# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
7661 | 2014-08-13T11:42:43 Z | myungwoo | Beads and wires (APIO14_beads) | C++ | 12 ms | 9728 KB |
#include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define MAXN 200005 #define pb push_back #define sz(v) ((int)(v).size()) int N,D[MAXN],E[MAXN]; vector <int> con[MAXN],conv[MAXN]; void dfs(int n,int p,int u) { int i; int sum = 0, mx1 = -2e9, mx2 = -2e9; for (i=sz(con[n]);i--;){ int k = con[n][i], v = conv[n][i]; if (k == p) continue; dfs(k,n,v); sum += max(D[k],E[k]); int diff = D[k]+v-max(D[k],E[k]); if (mx1 < diff) mx2 = mx1, mx1 = diff; else if (mx2 < diff) mx2 = diff; } D[n] = max(sum,mx1 > -2e9 && mx2 > -2e9 ? sum+mx1+mx2 : sum); E[n] = mx1 > -2e9 ? sum+mx1+u : -2e9; } int main() { int i,j,k; scanf("%d",&N); for (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,0); printf("%d\n",D[1]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 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 | 11 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9700 KB | Output is correct |
6 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 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 | 11 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9700 KB | Output is correct |
6 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 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 | 11 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9700 KB | Output is correct |
6 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 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 | 11 ms | 9728 KB | Output is correct |
5 | Correct | 10 ms | 9700 KB | Output is correct |
6 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |