# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
13043 | 2015-01-27T09:21:02 Z | baneling100 | Beads and wires (APIO14_beads) | C++ | 6 ms | 4992 KB |
#include <stdio.h> #include <algorithm> #include <vector> #define INF 0x7fffffff #define N_MAX 200000 using namespace std; struct rope { int next; int leng; }; vector <rope> Rope[N_MAX+1]; int N, Check[N_MAX+1], D1[N_MAX+1], D2[N_MAX+1], D3[N_MAX+1]; void input(void) { int i, in1, in2, in3; scanf("%d",&N); for(i=1 ; i<N ; i++) { scanf("%d %d %d",&in1,&in2,&in3); Rope[in1].push_back({in2,in3}); Rope[in2].push_back({in1,in3}); } } void treeDP(int now) { int i, j=Rope[now].size(), root=-1, max1, max2, temp; for(i=0 ; i<j ; i++) { if(Check[Rope[now][i].next]) root=i; else { Check[Rope[now][i].next]=1; treeDP(Rope[now][i].next); } } if(root>=0) D1[now]=Rope[now][root].leng; max1=max2=-INF; for(i=0 ; i<j ; i++) if(i!=root) { temp=max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next])); D1[now]+=temp; D2[now]+=temp; D3[now]+=temp; temp=Rope[now][i].leng-temp+max(D2[Rope[now][i].next],D3[Rope[now][i].next]); if(max1<temp) { max2=max1; max1=temp; } else if(max2<temp) max2=temp; } if(max1==-INF || root==-1) D1[now]=0; else D1[now]+=max1; if(max1==-INF || max2==-INF) D2[now]=0; else D2[now]+=max1+max2; } int main(void) { input(); Check[1]=1; treeDP(1); printf("%d",max(D2[1],D3[1])); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4992 KB | Output is correct |
2 | Correct | 5 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4992 KB | Output is correct |
2 | Correct | 5 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4992 KB | Output is correct |
2 | Correct | 5 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 4992 KB | Output is correct |
2 | Correct | 5 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |