# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
13477 | 2015-02-21T20:16:23 Z | ainta | Beads and wires (APIO14_beads) | C++ | 350 ms | 31888 KB |
#include<stdio.h> #include<algorithm> #include<vector> #define INF 999999999 using namespace std; vector<int>E[200100], L[200100]; int pL[201000], n, D[201000][4]; void DFS(int a, int pp){ int i, x, t1, t2, t3, t4, S = 0, S2 = 0, M1, M2, t, tt, M3, M4, x1, x3, MM, MM2; for (i = 0; i < E[a].size(); i++){ if (E[a][i] != pp){ pL[E[a][i]] = L[a][i]; DFS(E[a][i], a); } } D[a][1] = D[a][2] = D[a][3] = -INF; MM2 = MM = M1 = M2 = M3 = M4 = -INF; for (i = 0; i < E[a].size(); i++){ x = E[a][i]; if (x == pp)continue; t1 = D[x][0], t2 = D[x][1] + pL[x]; t = max(t1, t2); S += t; t3 = D[x][2], t4 = D[x][3] + pL[x]; tt = max(t3, t4); MM = max(MM, tt - t); t1 = D[x][0] + pL[x] - t; t2 = D[x][2] + pL[x] - t; MM2 = max(MM2, t2); if (M1 < t1){ M2 = M1; M1 = t1, x1 = i; } else if (M2 < t1)M2 = t1; if (M3 < t2){ M4 = M3; M3 = t2, x3 = i; } else if (M4 < t2)M4 = t2; } D[a][0] = S; if (!E[a].size())return; D[a][1] = S + M1; D[a][2] = S + MM; if (E[a].size() >= 2){ t1 = M1 + M2; if (x1 == x3)t2 = max(M1 + M4, M2 + M3); else t2 = M1 + M3; D[a][2] = max(D[a][2], S + max(t1, t2)); } D[a][3] = S + MM2; } int main(){ int i, a, b, d; scanf("%d", &n); for (i = 1; i < n; i++){ scanf("%d%d%d", &a, &b, &d); E[a].push_back(b); E[b].push_back(a); L[a].push_back(d); L[b].push_back(d); } DFS(1, 0); printf("%d\n", max(D[1][0], D[1][2])); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 9 ms | 9728 KB | Output is correct |
6 | Correct | 9 ms | 9728 KB | Output is correct |
7 | Correct | 9 ms | 9728 KB | Output is correct |
8 | Correct | 9 ms | 9728 KB | Output is correct |
9 | Correct | 10 ms | 9728 KB | Output is correct |
10 | Correct | 10 ms | 9728 KB | Output is correct |
11 | Correct | 10 ms | 9728 KB | Output is correct |
12 | Correct | 9 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 9 ms | 9728 KB | Output is correct |
6 | Correct | 9 ms | 9728 KB | Output is correct |
7 | Correct | 9 ms | 9728 KB | Output is correct |
8 | Correct | 9 ms | 9728 KB | Output is correct |
9 | Correct | 10 ms | 9728 KB | Output is correct |
10 | Correct | 10 ms | 9728 KB | Output is correct |
11 | Correct | 10 ms | 9728 KB | Output is correct |
12 | Correct | 9 ms | 9728 KB | Output is correct |
13 | Correct | 12 ms | 9728 KB | Output is correct |
14 | Correct | 10 ms | 9700 KB | Output is correct |
15 | Correct | 10 ms | 9728 KB | Output is correct |
16 | Correct | 10 ms | 9728 KB | Output is correct |
17 | Correct | 10 ms | 9728 KB | Output is correct |
18 | Correct | 10 ms | 9728 KB | Output is correct |
19 | Correct | 10 ms | 9728 KB | Output is correct |
20 | Correct | 10 ms | 9728 KB | Output is correct |
21 | Correct | 9 ms | 9728 KB | Output is correct |
22 | Correct | 9 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 9 ms | 9728 KB | Output is correct |
6 | Correct | 9 ms | 9728 KB | Output is correct |
7 | Correct | 9 ms | 9728 KB | Output is correct |
8 | Correct | 9 ms | 9728 KB | Output is correct |
9 | Correct | 10 ms | 9728 KB | Output is correct |
10 | Correct | 10 ms | 9728 KB | Output is correct |
11 | Correct | 10 ms | 9728 KB | Output is correct |
12 | Correct | 9 ms | 9728 KB | Output is correct |
13 | Correct | 12 ms | 9728 KB | Output is correct |
14 | Correct | 10 ms | 9700 KB | Output is correct |
15 | Correct | 10 ms | 9728 KB | Output is correct |
16 | Correct | 10 ms | 9728 KB | Output is correct |
17 | Correct | 10 ms | 9728 KB | Output is correct |
18 | Correct | 10 ms | 9728 KB | Output is correct |
19 | Correct | 10 ms | 9728 KB | Output is correct |
20 | Correct | 10 ms | 9728 KB | Output is correct |
21 | Correct | 9 ms | 9728 KB | Output is correct |
22 | Correct | 9 ms | 9728 KB | Output is correct |
23 | Correct | 13 ms | 10112 KB | Output is correct |
24 | Correct | 13 ms | 10112 KB | Output is correct |
25 | Correct | 14 ms | 10112 KB | Output is correct |
26 | Correct | 18 ms | 10624 KB | Output is correct |
27 | Correct | 16 ms | 10624 KB | Output is correct |
28 | Correct | 16 ms | 10624 KB | Output is correct |
29 | Correct | 17 ms | 10624 KB | Output is correct |
30 | Correct | 16 ms | 10624 KB | Output is correct |
31 | Correct | 17 ms | 10984 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 9 ms | 9728 KB | Output is correct |
6 | Correct | 9 ms | 9728 KB | Output is correct |
7 | Correct | 9 ms | 9728 KB | Output is correct |
8 | Correct | 9 ms | 9728 KB | Output is correct |
9 | Correct | 10 ms | 9728 KB | Output is correct |
10 | Correct | 10 ms | 9728 KB | Output is correct |
11 | Correct | 10 ms | 9728 KB | Output is correct |
12 | Correct | 9 ms | 9728 KB | Output is correct |
13 | Correct | 12 ms | 9728 KB | Output is correct |
14 | Correct | 10 ms | 9700 KB | Output is correct |
15 | Correct | 10 ms | 9728 KB | Output is correct |
16 | Correct | 10 ms | 9728 KB | Output is correct |
17 | Correct | 10 ms | 9728 KB | Output is correct |
18 | Correct | 10 ms | 9728 KB | Output is correct |
19 | Correct | 10 ms | 9728 KB | Output is correct |
20 | Correct | 10 ms | 9728 KB | Output is correct |
21 | Correct | 9 ms | 9728 KB | Output is correct |
22 | Correct | 9 ms | 9728 KB | Output is correct |
23 | Correct | 13 ms | 10112 KB | Output is correct |
24 | Correct | 13 ms | 10112 KB | Output is correct |
25 | Correct | 14 ms | 10112 KB | Output is correct |
26 | Correct | 18 ms | 10624 KB | Output is correct |
27 | Correct | 16 ms | 10624 KB | Output is correct |
28 | Correct | 16 ms | 10624 KB | Output is correct |
29 | Correct | 17 ms | 10624 KB | Output is correct |
30 | Correct | 16 ms | 10624 KB | Output is correct |
31 | Correct | 17 ms | 10984 KB | Output is correct |
32 | Correct | 58 ms | 13956 KB | Output is correct |
33 | Correct | 62 ms | 13928 KB | Output is correct |
34 | Correct | 53 ms | 13944 KB | Output is correct |
35 | Correct | 339 ms | 26744 KB | Output is correct |
36 | Correct | 350 ms | 26772 KB | Output is correct |
37 | Correct | 338 ms | 26744 KB | Output is correct |
38 | Correct | 238 ms | 27700 KB | Output is correct |
39 | Correct | 235 ms | 27732 KB | Output is correct |
40 | Correct | 237 ms | 27748 KB | Output is correct |
41 | Correct | 314 ms | 31888 KB | Output is correct |