UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214165#2045. cnodgd801356ms37408kbC++112.6kb2024-11-15 21:14:172024-11-15 23:27:24

answer

#include <bits/stdc++.h>

using namespace std;

const int BUFFER_SIZE = 1 << 20;
char rb[BUFFER_SIZE], *rp = rb, *rt = rb;
inline char read_char() {
    return rp == rt ? (rt = rb + fread(rb, 1, BUFFER_SIZE, stdin), rp = rb, *rp ++) : *rp ++;
}
inline int read_int() {
    int x = 0;
    char ch = read_char(), flag = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) {
        ch = read_char();
    }
    if (ch == '-') {
        flag = 1;
        ch = read_char();
    }
    for (x = 0; ch >= '0' && ch <= '9'; ch = read_char()) {
        x = x * 10 + (ch - '0');
    }
    return flag ? -x : x;
}
inline int read_string(char* s) {
    char* s0 = s;
    for (char ch = read_char(); ch > ' '; ch = read_char()) {
        *s ++ = ch;
    }
    return s - s0;
}

char wb[BUFFER_SIZE], *wp = wb;
inline void write_flush() {
    fwrite(wb, 1, wp - wb, stdout);
    wp = wb;
}
inline void write_char(char c) {
    *wp ++ = c;
    if (wp == wb + BUFFER_SIZE) {
        write_flush();
    }
}
inline void write_string(const char* s) {
    for (; *s; s ++) {
        write_char(*s);
    }

}

const int MAX_N = 500000 + 5;
typedef long long i64;

int N;
int a[MAX_N], f[MAX_N];
i64 w[MAX_N], c[MAX_N], ans;
vector<int> son[MAX_N];
struct Node {
    i64 w, c;
    int i;
    bool operator < (const Node &t) const {
        return w * t.c > t.w * c;
    }
};
priority_queue<Node> pq;

int get_fath(int i) {
    return f[i] == i ? i : f[i] = get_fath(f[i]);
}

int main() {
    N = read_int();
    for (int i = 1; i <= N; i ++) {
        a[i] = read_int();
        
        f[i] = i;
    }
    for (int i = 1; i <= N; i ++) {
        w[i] = read_int();
        c[i] = 1;
        ans += w[i];
        pq.push((Node){w[i], c[i], i});
    }
    while (pq.size()) {
        auto tmp = pq.top();
        pq.pop();
        int i = tmp.i;
        if (c[i] != tmp.c) continue;
        if (!a[i]) continue;
        int j = get_fath(a[i]);
        if (j == i) {
            printf("-1\n");
            return 0;
        }
        if (w[i] * c[j] < w[j] * c[i]) {
            ans += c[j] * w[i];
            f[i] = j;
            w[j] += w[i];
            c[j] += c[i];
            pq.push((Node){w[j], c[j], j});
        }
    }
    for (int i = 1; i <= N; i ++) {
        if (f[i] != i) continue;
        pq.push((Node){w[i], c[i], i});
    }
    while (pq.size()) {
        auto tmp = pq.top();
        pq.pop();
        int i = tmp.i;
        int j = get_fath(a[i]);
        ans += c[j] * w[i];
        f[i] = j;
        w[j] += w[i];
        c[j] += c[i];
    }
    printf("%lld\n", ans);
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 4ms
memory: 12924kb

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: 4ms
memory: 12936kb

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: 4ms
memory: 12936kb

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: 4ms
memory: 12940kb

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: 0
Wrong Answer
time: 3ms
memory: 13020kb

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:

37414848

result:

wrong answer 1st words differ - expected: '37419575', found: '37414848'

Test #6:

score: 10
Accepted
time: 0ms
memory: 13020kb

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: 67ms
memory: 18732kb

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: 97ms
memory: 18728kb

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: 0
Wrong Answer
time: 558ms
memory: 37408kb

input:

500000
331714 145478 6577 175958 171774 304559 166867 26414 92325 132061 8297 12915 470473 419957 48...

output:

4728510666048798015

result:

wrong answer 1st words differ - expected: '4728510666048798028', found: '4728510666048798015'

Test #10:

score: 10
Accepted
time: 615ms
memory: 37408kb

input:

500000
392409 161541 72825 120014 449034 320962 490925 62120 211235 236719 211792 410060 31166 20275...

output:

1604788177397380986

result:

ok "1604788177397380986"