Task: | Sadonkorjuu |
Sender: | stpn129 |
Submission time: | 2022-11-06 12:18:55 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 33 |
#2 | ACCEPTED | 67 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2 | details |
#2 | ACCEPTED | 0.00 s | 1, 2 | details |
#3 | ACCEPTED | 0.00 s | 1, 2 | details |
#4 | ACCEPTED | 0.00 s | 1, 2 | details |
#5 | ACCEPTED | 0.00 s | 1, 2 | details |
#6 | ACCEPTED | 0.01 s | 1, 2 | details |
#7 | ACCEPTED | 0.15 s | 2 | details |
#8 | ACCEPTED | 0.01 s | 1, 2 | details |
#9 | ACCEPTED | 0.18 s | 2 | details |
#10 | ACCEPTED | 0.01 s | 1, 2 | details |
#11 | ACCEPTED | 0.14 s | 2 | details |
#12 | ACCEPTED | 0.25 s | 2 | details |
#13 | ACCEPTED | 0.12 s | 2 | details |
#14 | ACCEPTED | 0.10 s | 2 | details |
#15 | ACCEPTED | 0.01 s | 1, 2 | details |
#16 | ACCEPTED | 0.01 s | 1, 2 | details |
#17 | ACCEPTED | 0.01 s | 1, 2 | details |
#18 | ACCEPTED | 0.01 s | 1, 2 | details |
#19 | ACCEPTED | 0.01 s | 1, 2 | details |
#20 | ACCEPTED | 0.01 s | 1, 2 | details |
#21 | ACCEPTED | 0.12 s | 2 | details |
#22 | ACCEPTED | 0.11 s | 2 | details |
#23 | ACCEPTED | 0.12 s | 2 | details |
#24 | ACCEPTED | 0.01 s | 1, 2 | details |
#25 | ACCEPTED | 0.12 s | 2 | details |
#26 | ACCEPTED | 0.01 s | 1, 2 | details |
#27 | ACCEPTED | 0.10 s | 2 | details |
#28 | ACCEPTED | 0.01 s | 1, 2 | details |
#29 | ACCEPTED | 0.10 s | 2 | details |
#30 | ACCEPTED | 0.01 s | 1, 2 | details |
#31 | ACCEPTED | 0.12 s | 2 | details |
Code
#include "bits/stdc++.h"using namespace std;void init_code() {ios_base::sync_with_stdio(false);cin.tie(NULL);#ifndef ONLINE_JUDGEfreopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);#endif}const int inf = 1e9 + 1;signed main() {init_code();int n, k = 1000;cin >> n;vector<int> p(n + 1);vector<pair<int, int>> g[n + 1];for (int i = 1; i <= n; ++i) {cin >> p[i];}for (int i = 1; i < n; ++i) {int x, y, c;cin >> x >> y >> c;g[x].push_back({y, c});g[y].push_back({x, c});if (p[x] == 0) {g[0].push_back({x, 0});}if (p[y] == 0) {g[0].push_back({y, 0});}}long long res = 0;vector<int> dist(n + 1, inf), used(n + 1, 0);queue<int> bfs[k + 1];bfs[0].push(0);dist[0] = 0;int pos = 0, cnt = 1;while (cnt > 0) {while (bfs[pos % (k + 1)].empty()){++pos;}int u = bfs[pos % (k + 1)].front();bfs[pos % (k + 1)].pop();--cnt;if (used[u]) continue;used[u] = 1;for (pair<int, int> edge : g[u]) {int cost = edge.second, w = edge.first;if (dist[u] + cost < dist[w]) {if (dist[w] == inf) {res += dist[u] + cost;} else {res -= dist[w];res += dist[u] + cost;}dist[w] = dist[u] + cost;bfs[dist[w] % (k + 1)].push(w);++cnt;}}}cout << res << '\n';}
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1 0 |
correct output |
---|
0 |
user output |
---|
0 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 0 0 0 0 1 2 1 2 3 2 3 4 3 ... |
correct output |
---|
0 |
user output |
---|
0 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
4 1 0 1 1 1 2 10 2 3 20 2 4 30 |
correct output |
---|
60 |
user output |
---|
60 |
Test 4
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 1 1 1 0 1 2 10 2 3 20 3 4 30 ... |
correct output |
---|
80 |
user output |
---|
80 |
Test 5
Group: 1, 2
Verdict: ACCEPTED
input |
---|
5 0 1 0 1 1 1 2 1 2 3 5 3 4 3 ... |
correct output |
---|
6 |
user output |
---|
6 |
Test 6
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5506363 |
user output |
---|
5506363 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1795118520 |
user output |
---|
1795118520 |
Test 8
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 ... |
correct output |
---|
293576 |
user output |
---|
293576 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
816932444 |
user output |
---|
816932444 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
3089 |
user output |
---|
3089 |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
40839 |
user output |
---|
40839 |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
5683983203973 |
user output |
---|
5683983203973 |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 ... |
correct output |
---|
58572993 |
user output |
---|
58572993 |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
32755 |
user output |
---|
32755 |
Test 15
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
126238345 |
user output |
---|
126238345 |
Test 16
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 ... |
correct output |
---|
278678 |
user output |
---|
278678 |
Test 17
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 ... |
correct output |
---|
34929 |
user output |
---|
34929 |
Test 18
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1543963 |
user output |
---|
1543963 |
Test 19
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
39606 |
user output |
---|
39606 |
Test 20
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 0 1 0 1 0 0 0 0 1 1 0 0 0 1 ... |
correct output |
---|
321598 |
user output |
---|
321598 |
Test 21
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
978670626 |
user output |
---|
978670626 |
Test 22
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ... |
correct output |
---|
375218 |
user output |
---|
375218 |
Test 23
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 ... |
correct output |
---|
60422556 |
user output |
---|
60422556 |
Test 24
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
291990 |
user output |
---|
291990 |
Test 25
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
59607954 |
user output |
---|
59607954 |
Test 26
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
990 |
user output |
---|
990 |
Test 27
Group: 2
Verdict: ACCEPTED
input |
---|
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
199982 |
user output |
---|
199982 |
Test 28
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
7987 |
user output |
---|
7987 |
Test 29
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
3137875 |
user output |
---|
3137875 |
Test 30
Group: 1, 2
Verdict: ACCEPTED
input |
---|
1000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
4657693 |
user output |
---|
4657693 |
Test 31
Group: 2
Verdict: ACCEPTED
input |
---|
200000 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1652889357 |
user output |
---|
1652889357 |