# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
15854 | 2015-07-31T13:15:10 Z | myungwoo | Beads and wires (APIO14_beads) | C++14 | 1000 ms | 10112 KB |
#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) int N; int D[MAXN], E[MAXN]; int up[MAXN], V[MAXN]; vector <int> con[MAXN], conv[MAXN]; void dfs(int n, int from) { vector <int> arr; for (int i=sz(con[n]);i--;){ int t = con[n][i], v = conv[n][i]; if (t == from) continue; up[t] = v; dfs(t, n); arr.pb(t); } D[n] = E[n] = 0; for (int t: arr){ V[t] = max(D[t], E[t]); D[n] += V[t]; } for (int t: arr){ E[n] = max(E[n], D[n] - V[t] + D[t] + up[t] + up[n]); } } int main() { scanf("%d", &N); for (int i=1;i<N;i++){ int a, b, c; scanf("%d%d%d", &a, &b, &c); con[a].pb(b); conv[a].pb(c); con[b].pb(a); conv[b].pb(c); } int ans = 0; for (int i=1;i<=N;i++){ dfs(i, 0); ans = max(ans, D[i]); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 9 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Correct | 10 ms | 9728 KB | Output is correct |
7 | Correct | 10 ms | 9728 KB | Output is correct |
8 | Correct | 10 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 | 10 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 9 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Correct | 10 ms | 9728 KB | Output is correct |
7 | Correct | 10 ms | 9728 KB | Output is correct |
8 | Correct | 10 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 | 10 ms | 9728 KB | Output is correct |
13 | Correct | 10 ms | 9728 KB | Output is correct |
14 | Correct | 11 ms | 9728 KB | Output is correct |
15 | Correct | 11 ms | 9728 KB | Output is correct |
16 | Correct | 12 ms | 9728 KB | Output is correct |
17 | Correct | 12 ms | 9728 KB | Output is correct |
18 | Correct | 12 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 | 10 ms | 9728 KB | Output is correct |
22 | Correct | 11 ms | 9728 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 9 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Correct | 10 ms | 9728 KB | Output is correct |
7 | Correct | 10 ms | 9728 KB | Output is correct |
8 | Correct | 10 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 | 10 ms | 9728 KB | Output is correct |
13 | Correct | 10 ms | 9728 KB | Output is correct |
14 | Correct | 11 ms | 9728 KB | Output is correct |
15 | Correct | 11 ms | 9728 KB | Output is correct |
16 | Correct | 12 ms | 9728 KB | Output is correct |
17 | Correct | 12 ms | 9728 KB | Output is correct |
18 | Correct | 12 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 | 10 ms | 9728 KB | Output is correct |
22 | Correct | 11 ms | 9728 KB | Output is correct |
23 | Execution timed out | 1068 ms | 10112 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 9 ms | 9728 KB | Output is correct |
4 | Correct | 9 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Correct | 10 ms | 9728 KB | Output is correct |
7 | Correct | 10 ms | 9728 KB | Output is correct |
8 | Correct | 10 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 | 10 ms | 9728 KB | Output is correct |
13 | Correct | 10 ms | 9728 KB | Output is correct |
14 | Correct | 11 ms | 9728 KB | Output is correct |
15 | Correct | 11 ms | 9728 KB | Output is correct |
16 | Correct | 12 ms | 9728 KB | Output is correct |
17 | Correct | 12 ms | 9728 KB | Output is correct |
18 | Correct | 12 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 | 10 ms | 9728 KB | Output is correct |
22 | Correct | 11 ms | 9728 KB | Output is correct |
23 | Execution timed out | 1068 ms | 10112 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |