# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
908139 | 2024-01-16T08:27:06 Z | duckindog | Beads and wires (APIO14_beads) | C++14 | 2 ms | 6492 KB |
// from duckindog wth depression #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int n; vector<pair<int, int>> ad[N]; int f[2][N]; int dfs(int u, int pre = 0) { int ret = 0; int all = -1e8, none = -1e8; for (auto duck : ad[u]) { int v, w; tie(v, w) = duck; if (v == pre) continue; if (all == -1e15) all = 0; dfs(v, u); ret = max(ret, f[0][v]); int best = max(f[1][v] + w, f[0][v]); all += best; none = max(none, f[0][v] + w - best); } f[0][u] = max(0, all); f[1][u] = all + none; return max(ret, f[0][u]); } int32_t main() { cin.tie(0)->sync_with_stdio(0); if (fopen("duck.inp", "r")) { freopen("duck.inp", "r", stdin); freopen("duck.out", "w", stdout); } cin >> n; for (int i = 1; i < n; ++i) { int u, v, w; cin >> u >> v >> w; ad[u].push_back({v, w}); ad[v].push_back({u, w}); } int answer = 0; for (int i = 1; i <= n; ++i) { answer = max(answer, dfs(i)); } cout << answer; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 6492 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |