# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
122331 | 2019-06-28T05:03:20 Z | 임유진(#2991) | Beads and wires (APIO14_beads) | C++14 | 6 ms | 5120 KB |
#include<stdio.h> #include<vector> using namespace std; #define MAXN 200005 typedef long long lint; typedef pair<lint, lint> pll; const lint LINF=1ll<<50; vector<pll> e[MAXN]; pll par[MAXN]; lint D[MAXN], P[MAXN]; void dfs(lint x){ lint psum=0ll; lint mx[2]={-LINF, -LINF}; for(auto a:e[x]) if(a.second!=par[x].second){ par[a.second]=make_pair(a.first, x); dfs(a.second); psum+=P[a.second]; lint t=D[a.second]-P[a.second]+a.first; mx[1]=max(t, mx[1]); if(mx[1]>mx[0]) swap(mx[0], mx[1]); } D[x]=psum+max(0ll, mx[0]+mx[1]); P[x]=max(D[x], psum+mx[0]+par[x].first); } int main(){ lint N; lint a[MAXN], b[MAXN], c[MAXN]; scanf("%lld", &N); for(lint i=0; i<N-1; i++) scanf("%lld%lld%lld", a+i, b+i, c+i); for(lint i=0; i<N-1; i++){ e[a[i]].push_back(make_pair(c[i], b[i])); e[b[i]].push_back(make_pair(c[i], a[i])); } par[1]=make_pair(0ll, 0ll); dfs(1ll); printf("%lld", D[1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 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 | 5 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 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 | 5 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 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 | 5 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 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 | 5 ms | 4992 KB | Output is correct |
5 | Correct | 5 ms | 4992 KB | Output is correct |
6 | Incorrect | 6 ms | 5120 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |