# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
363789 | 2021-02-07T09:26:50 Z | BartolM | Beads and wires (APIO14_beads) | C++17 | 5 ms | 4972 KB |
#include <bits/stdc++.h> using namespace std; #define X first #define Y second #define mp make_pair #define pb push_back typedef long long ll; typedef pair <int, int> pii; typedef pair <int, pii> pip; typedef pair <pii, int> ppi; typedef pair <ll, ll> pll; const int INF=0x3f3f3f3f; const int N=2e5+5; int n; vector <pii> ls[N]; int dp[N][2]; void rek(int node, int fl, int par) { for (pii sus:ls[node]) { if (sus.X!=par) { rek(sus.X, 0, node); rek(sus.X, 1, node); } } int maxi[2]={-INF, -INF}; int sum0=0; for (pii sus:ls[node]) { int x; if (sus.X==par) { if (fl) continue; x=sus.Y; } else { sum0+=dp[sus.X][0]; x=dp[sus.X][1]-dp[sus.X][0]+sus.Y; } for (int i=0; i<2; ++i) if (x>maxi[i]) swap(x, maxi[i]); } dp[node][fl]=max(sum0, sum0+maxi[0]+maxi[1]); } void load() { scanf("%d", &n); for (int i=0; i<n-1; ++i) { int a, b, c; scanf("%d %d %d", &a, &b, &c); ls[a].pb(mp(b, c)); ls[b].pb(mp(a, c)); } } int main() { load(); rek(1, 1, 1); printf("%d\n", dp[1][1]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 5 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 4 ms | 4972 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Incorrect | 4 ms | 4972 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 5 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 4 ms | 4972 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Incorrect | 4 ms | 4972 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 5 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 4 ms | 4972 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Incorrect | 4 ms | 4972 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 5 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 4 ms | 4972 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Incorrect | 4 ms | 4972 KB | Output isn't correct |
7 | Halted | 0 ms | 0 KB | - |