QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#690516 | #6241. 排列 | propane | 100 ✓ | 275ms | 48104kb | C++20 | 1.7kb | 2024-10-30 22:48:01 | 2024-10-30 22:48:01 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<queue>
#include<array>
using namespace std;
using LL = long long;
const int maxn = 5e5 + 5;
int p[maxn], sz[maxn], fa[maxn];
vector<int> g[maxn];
LL w[maxn];
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
if (x != y){
p[x] = y;
sz[y] += sz[x];
return;
}
}
struct Node{
LL sum, sz; int id;
bool operator<(const Node &t) const {
return sum * t.sz > t.sum * sz;
}
};
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 0; i <= n; i++){
p[i] = i;
sz[i] = 1;
}
for(int i = 1; i <= n; i++){
int x;
cin >> x;
fa[i] = x;
g[x].push_back(i);
merge(x, i);
}
if (sz[find(0)] != n + 1){
cout << -1 << '\n';
return 0;
}
for(int i = 0; i <= n; i++) sz[i] = 1;
priority_queue<Node> q;
LL ans = 0;
for(int i = 1; i <= n; i++){
cin >> w[i];
sz[i] = 1;
q.push({w[i], 1, i});
}
sz[0] = 1;
for(int i = 0; i <= n; i++){
p[i] = i;
}
while(!q.empty()){
auto [sum, s, x] = q.top();
q.pop();
if (s != sz[find(x)]) continue;
int t = find(fa[x]);
ans += sum * sz[t];
w[t] += w[x];
sz[t] += sz[x];
p[x] = t;
if (t) q.push({w[t], sz[t], t});
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 2ms
memory: 9992kb
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 number(s): "-1"
Test #2:
score: 10
Accepted
time: 0ms
memory: 9896kb
input:
10 0 9 5 5 0 0 0 0 0 0 576848570 9374579 447058478 375476508 17899037 890199416 691424702 96833317 40700401 400369951
output:
27663373474
result:
ok 1 number(s): "27663373474"
Test #3:
score: 10
Accepted
time: 0ms
memory: 9928kb
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 1 number(s): "571"
Test #4:
score: 10
Accepted
time: 1ms
memory: 9760kb
input:
15 10 0 13 14 0 0 4 9 0 2 0 0 0 0 10 699156165 159021634 857055962 44497989 345951671 893758337 84652794 960181918 701680230 427926415 685601506 579839946 224813409 49643923 574517449
output:
78062614530
result:
ok 1 number(s): "78062614530"
Test #5:
score: 10
Accepted
time: 2ms
memory: 9840kb
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 845 472 20 169 276 139 349 974 72 753 497 270 769 627 417 693 67 981 675 203 123 948 306 270 537 567 91 680 547 13 123 74 591 125 252 448 313 608 40 680 660 866 58 33 583 513 630 134 549 908 215 442 3...
output:
37419575
result:
ok 1 number(s): "37419575"
Test #6:
score: 10
Accepted
time: 0ms
memory: 10060kb
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 315 642 988 190 193 371 287 567 715 446 736 146 328 166 683 45 205 311 876 25 871 315 169 491 286 187 881 197 903 291 773 895 270 451 80 788 37 575 267 204 221 149 591 32 573 239 753 898 401 756 946 ...
output:
370124146702558
result:
ok 1 number(s): "370124146702558"
Test #7:
score: 10
Accepted
time: 47ms
memory: 17160kb
input:
100000 14420 84013 87193 82068 10374 79474 25939 9590 32198 3548 47938 85741 12568 14530 8858 60495 76879 88508 92355 39001 91887 44242 56198 69674 49298 17610 85793 94620 41209 0 13448 38154 44201 52912 52585 0 0 48658 65112 63102 66820 72053 98517 70739 4541 5762 97650 65562 93053 85877 60023 7503...
output:
37283654934273540
result:
ok 1 number(s): "37283654934273540"
Test #8:
score: 10
Accepted
time: 44ms
memory: 18840kb
input:
100000 26403 63914 61602 32321 29105 19251 73439 61190 72905 30337 25317 66634 83841 38470 96206 8489 90663 39165 68790 51978 20847 88796 83258 5805 54839 71322 69887 54104 59373 9227 21113 31790 4680 42578 14237 28713 9935 44028 8070 7201 6904 3282 76671 63856 12689 10204 51578 85748 85776 62557 58...
output:
140620474524379753
result:
ok 1 number(s): "140620474524379753"
Test #9:
score: 10
Accepted
time: 275ms
memory: 48104kb
input:
500000 331714 145478 6577 175958 171774 304559 166867 26414 92325 132061 8297 12915 470473 419957 483702 296146 264727 5044 347818 219740 145856 163914 238174 214629 221800 489750 181382 216835 222885 343241 43258 359531 185839 434336 458495 330659 49799 158239 15303 293963 391188 419292 371335 4002...
output:
4728510666048798028
result:
ok 1 number(s): "4728510666048798028"
Test #10:
score: 10
Accepted
time: 252ms
memory: 45544kb
input:
500000 392409 161541 72825 120014 449034 320962 490925 62120 211235 236719 211792 410060 31166 202758 251734 413493 458505 190309 308143 1305 120907 320156 413060 239031 95201 107602 39593 126597 186821 305505 440753 306136 440459 13190 294027 269116 18980 250503 355642 66638 395513 11629 159318 361...
output:
1604788177397380986
result:
ok 1 number(s): "1604788177397380986"