# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
15851 | 2015-07-31T11:34:34 Z | myungwoo | Beads and wires (APIO14_beads) | C++14 | 16 ms | 9728 KB |
#include <bits/stdc++.h> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(), (v).end() int N; int D[MAXN], E[MAXN], 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); V[t] = D[t] - max(D[t], E[t]) + up[t]; arr.pb(t); } sort(all(arr), [](const int &a, const int &b){ return V[a] > V[b]; }); D[n] = E[n] = 0; if (arr.empty()) return; for (int t: arr) D[n] += max(D[t], E[t]); E[n] = D[n]; if (sz(arr) > 1) D[n] += max(0, V[arr[0]] + V[arr[1]]); E[n] += up[n] + V[arr[0]]; } 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); } dfs(1, 0); printf("%d\n", D[1]); }
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 | 11 ms | 9728 KB | Output is correct |
4 | Correct | 16 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
7 | 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 | 11 ms | 9728 KB | Output is correct |
4 | Correct | 16 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
7 | 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 | 11 ms | 9728 KB | Output is correct |
4 | Correct | 16 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
7 | 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 | 11 ms | 9728 KB | Output is correct |
4 | Correct | 16 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9728 KB | Output is correct |
6 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |