ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214141 | #2045. c | Filberte | 100 | 1162ms | 42872kb | C++11 | 1.5kb | 2024-11-15 20:06:31 | 2024-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