QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#690516#6241. 排列propane100 ✓275ms48104kbC++201.7kb2024-10-30 22:48:012024-10-30 22:48:01

Judging History

你现在查看的是最新测评结果

  • [2024-10-30 22:48:01]
  • 评测
  • 测评结果:100
  • 用时:275ms
  • 内存:48104kb
  • [2024-10-30 22:48:01]
  • 提交

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';

}

詳細信息


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"