ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214165 | #2045. c | nodgd | 80 | 1356ms | 37408kb | C++11 | 2.6kb | 2024-11-15 21:14:17 | 2024-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;
}
Details
小提示:点击横条可展开更详细的信息
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"