# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
158441 | 2019-10-17T04:56:02 Z | arnold518 | Beads and wires (APIO14_beads) | C++14 | 6 ms | 4984 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; int N; vector<pii> adj[MAXN+10]; ll dp1[MAXN+10], dp2[MAXN+10]; void dfs(int now, int bef, int par) { vector<ll> V; ll S=0; for(pii nxt : adj[now]) { if(nxt.first==bef) continue; dfs(nxt.first, now, nxt.second); S+=max(dp1[nxt.first], dp2[nxt.first]); V.push_back(dp2[nxt.first]+nxt.second-max(dp1[nxt.first], dp2[nxt.first])); } sort(V.begin(), V.end(), greater<ll>()); dp2[now]=S; if(V.size()>1 && V[0]+V[1]>=0) dp2[now]+=V[0]+V[1]; if(V.size()<=0) dp1[now]=-987654321987654321; else dp1[now]=S+par+V[0]; //printf("%d %lld %lld\n", now, dp1[now], dp2[now]); } int main() { int i, j; scanf("%d", &N); for(i=1; i<N; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dfs(1, 1, 0); printf("%lld", dp2[1]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Incorrect | 6 ms | 4984 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Incorrect | 6 ms | 4984 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Incorrect | 6 ms | 4984 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4984 KB | Output is correct |
2 | Correct | 6 ms | 4984 KB | Output is correct |
3 | Correct | 6 ms | 4984 KB | Output is correct |
4 | Correct | 6 ms | 4984 KB | Output is correct |
5 | Correct | 6 ms | 4984 KB | Output is correct |
6 | Incorrect | 6 ms | 4984 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |