# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
122383 | 2019-06-28T06:39:32 Z | 이온조(#2989) | Beads and wires (APIO14_beads) | C++14 | 7 ms | 4992 KB |
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; vector<pii> adj[200009]; int D[2][200009]; int go(int x, int p, int pc) { for(auto& it: adj[x]) if(it.first != p) go(it.first, x, it.second); int m1 = -1e9, m2 = -1e9, s = 0; for(auto& it: adj[x]) if(it.first != p) s += max(D[0][it.first], D[1][it.first]); for(auto& it: adj[x]) if(it.first != p) { int n, c; tie(n, c) = it; int v = D[0][n] + c - max(D[0][n], D[1][n]); if(m1 <= v) m2 = m1, m1 = v; else if(m2 <= v) m2 = v; } if(m2 != -1e9) D[0][x] = s + m1 + m2; if(m1 != -1) D[1][x] = max(D[1][p], s + m1 + pc); } int main() { int N; scanf("%d",&N); for(int i=0; i<N-1; i++) { int u, v, w; scanf("%d%d%d",&u,&v,&w); adj[u].push_back({v, w}); adj[v].push_back({u, w}); } go(1, 1, -1e9); printf("%d", D[0][1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 4992 KB | Output is correct |
3 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 4992 KB | Output is correct |
3 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 4992 KB | Output is correct |
3 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 4992 KB | Output is correct |
2 | Correct | 7 ms | 4992 KB | Output is correct |
3 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |