ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214170 | #2045. c | KXG | 20 | 495ms | 18088kb | C++ | 1006b | 2024-11-15 21:23:21 | 2024-11-15 23:28:09 |
answer
#include <cstdio>
#include <algorithm>
using namespace std;
pair<int, int> w[500010];
int n, a[500010];
int fa[500010], siz[500010];
long long ans[500010], sum[500010];
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fx] = fy;
ans[fy] = ans[fx] + ans[fy] + siz[fy] * sum[fx];
siz[fy] += siz[fx];
sum[fy] += sum[fx];
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i].first);
w[i].second = i;
fa[i] = i;
siz[i] = 1;
sum[i] = w[i].first;
ans[i] = w[i].first;
}
sort(w + 1, w + n + 1);
for (int i = 1; i <= n; i++) {
merge(w[i].second, a[w[i].second]);
}
if (siz[0] != n) ans[0] = -1;
printf("%d\n", ans[0]);
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 2ms
memory: 4428kb
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: 0
Wrong Answer
time: 0ms
memory: 4432kb
input:
10 0 9 5 5 0 0 0 0 0 0 576848570 9374579 447058478 375476508 17899037 890199416 691424702 96833317 4...
output:
1893569698
result:
wrong answer 1st words differ - expected: '27663373474', found: '1893569698'
Test #3:
score: 10
Accepted
time: 0ms
memory: 4432kb
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: 0
Wrong Answer
time: 0ms
memory: 4432kb
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:
753203202
result:
wrong answer 1st words differ - expected: '78062614530', found: '753203202'
Test #5:
score: 0
Wrong Answer
time: 0ms
memory: 4456kb
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:
32999409
result:
wrong answer 1st words differ - expected: '37419575', found: '32999409'
Test #6:
score: 0
Wrong Answer
time: 0ms
memory: 4460kb
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:
757866342
result:
wrong answer 1st words differ - expected: '370124146702558', found: '757866342'
Test #7:
score: 0
Wrong Answer
time: 22ms
memory: 7164kb
input:
100000 14420 84013 87193 82068 10374 79474 25939 9590 32198 3548 47938 85741 12568 14530 8858 60495 ...
output:
-744048675
result:
wrong answer 1st words differ - expected: '37283654934273540', found: '-744048675'
Test #8:
score: 0
Wrong Answer
time: 33ms
memory: 7164kb
input:
100000 26403 63914 61602 32321 29105 19251 73439 61190 72905 30337 25317 66634 83841 38470 96206 848...
output:
2145510419
result:
wrong answer 1st words differ - expected: '140620474524379753', found: '2145510419'
Test #9:
score: 0
Wrong Answer
time: 222ms
memory: 18088kb
input:
500000 331714 145478 6577 175958 171774 304559 166867 26414 92325 132061 8297 12915 470473 419957 48...
output:
-1604234699
result:
wrong answer 1st words differ - expected: '4728510666048798028', found: '-1604234699'
Test #10:
score: 0
Wrong Answer
time: 216ms
memory: 18080kb
input:
500000 392409 161541 72825 120014 449034 320962 490925 62120 211235 236719 211792 410060 31166 20275...
output:
1562980793
result:
wrong answer 1st words differ - expected: '1604788177397380986', found: '1562980793'