# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
580878 | 2022-06-22T04:59:19 Z | 박상훈(#8359) | Beads and wires (APIO14_beads) | C++17 | 3 ms | 5004 KB |
#include <bits/stdc++.h> typedef long long ll; using namespace std; vector<pair<int, int>> adj[200200]; int dp[200200][2]; void dfs(int s, int pa = -1, int w0 = 0){ vector<int> C; for (auto &[v, w]:adj[s]) if (v!=pa){ dfs(v, s, w); C.push_back(dp[v][0] + w - dp[v][1]); dp[s][0] += dp[v][1]; dp[s][1] += dp[v][1]; } sort(C.begin(), C.end(), greater<int>()); for (int i=0;i+1<(int)C.size();i+=2){ if (i==2) break; if (C[i] + C[i+1] < 0) break; dp[s][0] += C[i] + C[i+1]; } if (C.empty()) return; dp[s][1] += w0 + C[0]; dp[s][1] = max(dp[s][0], dp[s][1]); } int main(){ int n; scanf("%d", &n); for (int i=0;i<n-1;i++){ int x, y, z; scanf("%d %d %d", &x, &y, &z); adj[x].emplace_back(y, z); adj[y].emplace_back(x, z); } dfs(1); printf("%d\n", dp[1][0]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5004 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 4948 KB | Output is correct |
4 | Correct | 3 ms | 5004 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Incorrect | 3 ms | 4948 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5004 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 4948 KB | Output is correct |
4 | Correct | 3 ms | 5004 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Incorrect | 3 ms | 4948 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5004 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 4948 KB | Output is correct |
4 | Correct | 3 ms | 5004 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Incorrect | 3 ms | 4948 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5004 KB | Output is correct |
2 | Correct | 3 ms | 4948 KB | Output is correct |
3 | Correct | 3 ms | 4948 KB | Output is correct |
4 | Correct | 3 ms | 5004 KB | Output is correct |
5 | Correct | 3 ms | 4948 KB | Output is correct |
6 | Incorrect | 3 ms | 4948 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |