UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214141#2045. cFilberte1001162ms42872kbC++111.5kb2024-11-15 20:06:312024-11-15 23:25:13

answer

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 5e5 + 100;
int n;
struct dsu1{
    int fa[N];
    void init(){for(int i = 0;i <= n;i++) fa[i] = i;}
    int find(int x){return x == fa[x] ? x : (fa[x] = find(fa[x]));}
    bool merge(int x, int y){
        x = find(x), y = find(y);
        if(x == y) return 0;
        fa[x] = y;
        return 1;
    }
}ns, T;
vector<int> g[N];
int Fat[N];
struct Nod{
    ll s, val;
    int sz, id;
    bool operator < (const Nod &ot) const{
        return s * ot.sz > ot.s * sz;
    }
    Nod operator + (const Nod & ot) const{
        Nod ret;
        ret.s = s + ot.s;
        ret.sz = sz + ot.sz;
        ret.id = id;
        ret.val = val + ot.val + ot.s * sz;
        return ret;
    }
}Cur[N];
priority_queue<Nod> pq;
bool vis[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;ns.init();T.init();
    for(int i = 1;i <= n;i++){
        cin >> Fat[i];
        if(!ns.merge(i, Fat[i])){
            cout << "-1\n";
            return 0;
        }
    }
    Cur[0] = {0, 0, 0, 0};
    for(int i = 1, x;i <= n;i++){
        cin >> x;
        Cur[i] = {x, x, 1, i};
        pq.push(Cur[i]);
    }
    while(!pq.empty()){
        int u = pq.top().id;
        pq.pop();
        if(!u || vis[u]) continue;
        vis[u] = 1;
        int pt = T.find(Fat[u]);
        T.merge(u, Fat[u]);
        Cur[pt] = Cur[pt] + Cur[u];
        pq.push(Cur[pt]);
    }
    cout << Cur[0].val << endl;
    return 0;

}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 7ms
memory: 12964kb

input:

10
2 8 3 4 1 2 4 8 5 8
1 2 8 1 10 2 9 8 8 8

output:

-1

result:

ok "-1"

Test #2:

score: 10
Accepted
time: 0ms
memory: 13008kb

input:

10
0 9 5 5 0 0 0 0 0 0
576848570 9374579 447058478 375476508 17899037 890199416 691424702 96833317 4...

output:

27663373474

result:

ok "27663373474"

Test #3:

score: 10
Accepted
time: 0ms
memory: 13008kb

input:

15
0 0 0 12 6 0 0 14 8 0 0 7 6 15 0
1 4 7 1 5 1 1 6 8 6 1 1 2 6 2

output:

571

result:

ok "571"

Test #4:

score: 10
Accepted
time: 0ms
memory: 13008kb

input:

15
10 0 13 14 0 0 4 9 0 2 0 0 0 0 10
699156165 159021634 857055962 44497989 345951671 893758337 8465...

output:

78062614530

result:

ok "78062614530"

Test #5:

score: 10
Accepted
time: 7ms
memory: 13100kb

input:

1000
144 384 112 973 710 47 773 579 421 233 4 657 112 596 133 780 803 571 300 804 34 291 507 270 79 ...

output:

37419575

result:

ok "37419575"

Test #6:

score: 10
Accepted
time: 5ms
memory: 13100kb

input:

1000
349 415 281 956 749 201 628 217 723 900 513 106 618 978 176 448 834 704 763 266 466 533 192 379...

output:

370124146702558

result:

ok "370124146702558"

Test #7:

score: 10
Accepted
time: 72ms
memory: 19080kb

input:

100000
14420 84013 87193 82068 10374 79474 25939 9590 32198 3548 47938 85741 12568 14530 8858 60495 ...

output:

37283654934273540

result:

ok "37283654934273540"

Test #8:

score: 10
Accepted
time: 67ms
memory: 19080kb

input:

100000
26403 63914 61602 32321 29105 19251 73439 61190 72905 30337 25317 66634 83841 38470 96206 848...

output:

140620474524379753

result:

ok "140620474524379753"

Test #9:

score: 10
Accepted
time: 532ms
memory: 42872kb

input:

500000
331714 145478 6577 175958 171774 304559 166867 26414 92325 132061 8297 12915 470473 419957 48...

output:

4728510666048798028

result:

ok "4728510666048798028"

Test #10:

score: 10
Accepted
time: 472ms
memory: 42872kb

input:

500000
392409 161541 72825 120014 449034 320962 490925 62120 211235 236719 211792 410060 31166 20275...

output:

1604788177397380986

result:

ok "1604788177397380986"

Extra Test:

score: 0
Extra Test Passed