# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
8579 | 2014-09-17T11:59:51 Z | dohyun0324 | 구슬과 끈 (APIO14_beads) | C++ | 15 ms | 14464 KB |
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; vector<int>con[200010]; vector<int>len[200010]; vector<int>d[200010]; int sum,x,y,c,n,D[200010],big,big1,big2,p1,p2,ch[200010],anc[200010]; void dfs(int x) { int i,j; ch[x]=1; for(i=0;i<con[x].size();i++) { if(ch[con[x][i]]==1){anc[x]=con[x][i]; continue;} dfs(con[x][i]); } big=0; for(i=0;i<con[x].size();i++) { if(anc[x]==con[x][i]) continue; sum=0; big=0; for(j=0;j<con[con[x][i]].size();j++) sum+=d[con[x][i]][j]; for(j=0;j<con[con[x][i]].size();j++) { if(con[con[x][i]][j]==x) continue; if(big<sum-d[con[x][i]][j]+D[con[con[x][i]][j]]+len[x][i]+len[con[x][i]][j]) { big=sum-d[con[x][i]][j]+D[con[con[x][i]][j]]+len[x][i]+len[con[x][i]][j]; } } d[x][i]=max(big,D[con[x][i]]); } big1=-2147483647; for(i=0;i<con[x].size();i++) { if(anc[x]==con[x][i]) continue; if(big1<D[con[x][i]]+len[x][i]-d[x][i]) { big1=D[con[x][i]]+len[x][i]-d[x][i]; p1=i; } } big2=-2147483647; for(i=0;i<con[x].size();i++) { if(anc[x]==con[x][i]) continue; if(i!=p1 && big2<D[con[x][i]]+len[x][i]-d[x][i]) { big2=D[con[x][i]]+len[x][i]-d[x][i]; p2=i; } } sum=0; for(i=0;i<con[x].size();i++) { if(anc[x]==con[x][i]) continue; sum+=d[x][i]; } if(big1==-2147483647 || big2==-2147483647) D[x]=sum; else D[x]=max(sum,sum+big1+big2); } int main() { int i; scanf("%d",&n); for(i=1;i<n;i++) { scanf("%d %d %d",&x,&y,&c); con[x].push_back(y); con[y].push_back(x); len[x].push_back(c); len[y].push_back(c); d[x].push_back(0); d[y].push_back(0); } dfs(1); printf("%d",D[1]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 14464 KB | Output is correct |
2 | Correct | 14 ms | 14464 KB | Output is correct |
3 | Correct | 15 ms | 14336 KB | Output is correct |
4 | Correct | 14 ms | 14328 KB | Output is correct |
5 | Correct | 15 ms | 14336 KB | Output is correct |
6 | Incorrect | 15 ms | 14464 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 14464 KB | Output is correct |
2 | Correct | 14 ms | 14464 KB | Output is correct |
3 | Correct | 15 ms | 14336 KB | Output is correct |
4 | Correct | 14 ms | 14328 KB | Output is correct |
5 | Correct | 15 ms | 14336 KB | Output is correct |
6 | Incorrect | 15 ms | 14464 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 14464 KB | Output is correct |
2 | Correct | 14 ms | 14464 KB | Output is correct |
3 | Correct | 15 ms | 14336 KB | Output is correct |
4 | Correct | 14 ms | 14328 KB | Output is correct |
5 | Correct | 15 ms | 14336 KB | Output is correct |
6 | Incorrect | 15 ms | 14464 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 14464 KB | Output is correct |
2 | Correct | 14 ms | 14464 KB | Output is correct |
3 | Correct | 15 ms | 14336 KB | Output is correct |
4 | Correct | 14 ms | 14328 KB | Output is correct |
5 | Correct | 15 ms | 14336 KB | Output is correct |
6 | Incorrect | 15 ms | 14464 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |