# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
122392 | 2019-06-28T06:55:12 Z | 이온조(#2989) | 구슬과 끈 (APIO14_beads) | C++14 | 6 ms | 5120 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; } D[0][x] = s; if(m2 != -1e9) D[0][x] = max(D[0][x], s + m1 + m2); if(m1 != -1) D[1][x] = max(D[1][x], 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}); } int rt; for(int i=1; i<=N; i++) if((int)adj[i].size() == 1) rt = i; go(rt, rt, -1e9); printf("%d", D[0][rt]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 5120 KB | Output is correct |
5 | Correct | 6 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 5120 KB | Output is correct |
5 | Correct | 6 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 5120 KB | Output is correct |
5 | Correct | 6 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 4992 KB | Output is correct |
2 | Correct | 6 ms | 4992 KB | Output is correct |
3 | Correct | 5 ms | 4992 KB | Output is correct |
4 | Correct | 6 ms | 5120 KB | Output is correct |
5 | Correct | 6 ms | 4992 KB | Output is correct |
6 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |