# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
908136 | 2024-01-16T08:24:25 Z | duckindog | Beads and wires (APIO14_beads) | C++14 | 1000 ms | 8792 KB |
// from duckindog wth depression #include<bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 10; int n; vector<pair<int, int>> ad[N]; int f[2][N]; void dfs(int u, int pre = 0) { int all = -1e15, none = -1e15; for (auto duck : ad[u]) { int v, w; tie(v, w) = duck; if (v == pre) continue; if (all == -1e15) all = 0; dfs(v, u); int best = max(f[1][v] + w, f[0][v]); all += best; none = max(none, f[0][v] + w - best); } f[0][u] = max(0ll, all); f[1][u] = all + none; } 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) { dfs(i); answer = max(answer, *max_element(f[0] + 1, f[0] + n + 1)); } cout << answer; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8028 KB | Output is correct |
2 | Correct | 2 ms | 8028 KB | Output is correct |
3 | Correct | 3 ms | 8028 KB | Output is correct |
4 | Correct | 2 ms | 8028 KB | Output is correct |
5 | Correct | 2 ms | 8104 KB | Output is correct |
6 | Correct | 3 ms | 8028 KB | Output is correct |
7 | Correct | 2 ms | 7884 KB | Output is correct |
8 | Correct | 3 ms | 8028 KB | Output is correct |
9 | Correct | 3 ms | 8028 KB | Output is correct |
10 | Correct | 3 ms | 8028 KB | Output is correct |
11 | Correct | 3 ms | 8284 KB | Output is correct |
12 | Correct | 2 ms | 8028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8028 KB | Output is correct |
2 | Correct | 2 ms | 8028 KB | Output is correct |
3 | Correct | 3 ms | 8028 KB | Output is correct |
4 | Correct | 2 ms | 8028 KB | Output is correct |
5 | Correct | 2 ms | 8104 KB | Output is correct |
6 | Correct | 3 ms | 8028 KB | Output is correct |
7 | Correct | 2 ms | 7884 KB | Output is correct |
8 | Correct | 3 ms | 8028 KB | Output is correct |
9 | Correct | 3 ms | 8028 KB | Output is correct |
10 | Correct | 3 ms | 8028 KB | Output is correct |
11 | Correct | 3 ms | 8284 KB | Output is correct |
12 | Correct | 2 ms | 8028 KB | Output is correct |
13 | Correct | 3 ms | 8028 KB | Output is correct |
14 | Correct | 2 ms | 8028 KB | Output is correct |
15 | Correct | 2 ms | 8028 KB | Output is correct |
16 | Correct | 3 ms | 8100 KB | Output is correct |
17 | Correct | 3 ms | 8280 KB | Output is correct |
18 | Correct | 4 ms | 8024 KB | Output is correct |
19 | Correct | 3 ms | 8028 KB | Output is correct |
20 | Correct | 3 ms | 8028 KB | Output is correct |
21 | Correct | 3 ms | 8028 KB | Output is correct |
22 | Correct | 3 ms | 8028 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8028 KB | Output is correct |
2 | Correct | 2 ms | 8028 KB | Output is correct |
3 | Correct | 3 ms | 8028 KB | Output is correct |
4 | Correct | 2 ms | 8028 KB | Output is correct |
5 | Correct | 2 ms | 8104 KB | Output is correct |
6 | Correct | 3 ms | 8028 KB | Output is correct |
7 | Correct | 2 ms | 7884 KB | Output is correct |
8 | Correct | 3 ms | 8028 KB | Output is correct |
9 | Correct | 3 ms | 8028 KB | Output is correct |
10 | Correct | 3 ms | 8028 KB | Output is correct |
11 | Correct | 3 ms | 8284 KB | Output is correct |
12 | Correct | 2 ms | 8028 KB | Output is correct |
13 | Correct | 3 ms | 8028 KB | Output is correct |
14 | Correct | 2 ms | 8028 KB | Output is correct |
15 | Correct | 2 ms | 8028 KB | Output is correct |
16 | Correct | 3 ms | 8100 KB | Output is correct |
17 | Correct | 3 ms | 8280 KB | Output is correct |
18 | Correct | 4 ms | 8024 KB | Output is correct |
19 | Correct | 3 ms | 8028 KB | Output is correct |
20 | Correct | 3 ms | 8028 KB | Output is correct |
21 | Correct | 3 ms | 8028 KB | Output is correct |
22 | Correct | 3 ms | 8028 KB | Output is correct |
23 | Correct | 438 ms | 8456 KB | Output is correct |
24 | Correct | 430 ms | 8448 KB | Output is correct |
25 | Correct | 402 ms | 8284 KB | Output is correct |
26 | Execution timed out | 1018 ms | 8792 KB | Time limit exceeded |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 8028 KB | Output is correct |
2 | Correct | 2 ms | 8028 KB | Output is correct |
3 | Correct | 3 ms | 8028 KB | Output is correct |
4 | Correct | 2 ms | 8028 KB | Output is correct |
5 | Correct | 2 ms | 8104 KB | Output is correct |
6 | Correct | 3 ms | 8028 KB | Output is correct |
7 | Correct | 2 ms | 7884 KB | Output is correct |
8 | Correct | 3 ms | 8028 KB | Output is correct |
9 | Correct | 3 ms | 8028 KB | Output is correct |
10 | Correct | 3 ms | 8028 KB | Output is correct |
11 | Correct | 3 ms | 8284 KB | Output is correct |
12 | Correct | 2 ms | 8028 KB | Output is correct |
13 | Correct | 3 ms | 8028 KB | Output is correct |
14 | Correct | 2 ms | 8028 KB | Output is correct |
15 | Correct | 2 ms | 8028 KB | Output is correct |
16 | Correct | 3 ms | 8100 KB | Output is correct |
17 | Correct | 3 ms | 8280 KB | Output is correct |
18 | Correct | 4 ms | 8024 KB | Output is correct |
19 | Correct | 3 ms | 8028 KB | Output is correct |
20 | Correct | 3 ms | 8028 KB | Output is correct |
21 | Correct | 3 ms | 8028 KB | Output is correct |
22 | Correct | 3 ms | 8028 KB | Output is correct |
23 | Correct | 438 ms | 8456 KB | Output is correct |
24 | Correct | 430 ms | 8448 KB | Output is correct |
25 | Correct | 402 ms | 8284 KB | Output is correct |
26 | Execution timed out | 1018 ms | 8792 KB | Time limit exceeded |
27 | Halted | 0 ms | 0 KB | - |