UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214170#2045. cKXG20495ms18088kbC++1006b2024-11-15 21:23:212024-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'