# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
23718 | 2017-05-22T17:29:12 Z | abcdef6199 | Beads and wires (APIO14_beads) | C++ | 6 ms | 4992 KB |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> II; const int N = (int) 2e5 + 10; int n, dp[N][2]; vector<II> adj[N]; void DFS(int u, int p = -1) { if ((int) adj[u].size() == 1 && adj[u][0].first == p) { dp[u][0] = 0; dp[u][1] = -2e9; return; } vector<int> delta; for (int i = 0; i < (int) adj[u].size(); ++i) { int v = adj[u][i].first; int w = adj[u][i].second; if (v != p) { DFS(v, u); int f = max(dp[v][0], w + dp[v][1]); dp[u][0] += f; dp[u][1] += f; delta.push_back(w + dp[v][0] - f); } } sort(delta.begin(), delta.end(), greater<int>()); dp[u][1] += delta[0]; if (delta.size() >= 2) dp[u][0] += delta[0] + delta[1]; } int main() { #ifdef LOCAL freopen("inp", "r", stdin); freopen("out", "w", stdout); #endif scanf("%d", &n); for (int i = 1; i <= n - 1; ++i) { int u, v, w; scanf("%d%d%d", &u, &v, &w); adj[u].push_back(II(v, w)); adj[v].push_back(II(u, w)); } DFS(1); printf("%d", dp[1][0]); 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 | 6 ms | 4992 KB | Output is correct |
4 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
5 | 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 | 6 ms | 4992 KB | Output is correct |
4 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
5 | 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 | 6 ms | 4992 KB | Output is correct |
4 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
5 | 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 | 6 ms | 4992 KB | Output is correct |
4 | Incorrect | 5 ms | 4992 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |