# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48301 | 2018-05-11T14:11:32 Z | octopuses | Beads and wires (APIO14_beads) | C++17 | 268 ms | 20400 KB |
#include <bits/stdc++.h> #define ll long long #define fr first #define sc second #define M (ll)(3e17) using namespace std; const int N = 200020; vector < pair < int, int > > G[N]; int n; ll A[N], B[N], answer, par[N]; void go(int v, int p = 0) { ll mx1 = -2e9, mx2 = -2e9, child = 0, tot = 0; for(int i = 0; i < G[v].size(); ++ i) { int to = G[v][i].first; if(to == p) { par[v] = G[v][i].second; swap(G[v][i], G[v].back()); G[v].pop_back(); i --; continue; } go(to, v); tot += A[to]; child ++; } A[v] = B[v] = tot; for(int i = 0; i < G[v].size(); ++ i) { int to = G[v][i].first; if(to == p) continue; A[v] = max(A[v], tot - A[to] + B[to] + par[v] + G[v][i].second); } } void dfs(int v, ll a, ll b) { ll tot = a; ll mx1, mx2; mx1 = b - a + par[v]; mx2 = -2e9; for(int i = 0; i < G[v].size(); ++ i) { int to = G[v][i].first; tot += A[to]; if(mx1 < B[to] - A[to] + G[v][i].second) { mx2 = mx1; mx1 = B[to] - A[to] + G[v][i].second; } else if(mx2 < B[to] - A[to] + G[v][i].second) mx2 = B[to] - A[to] + G[v][i].second; } answer = max(answer, tot); for(int i = 0; i < G[v].size(); ++ i) { int to = G[v][i].first; ll now = mx1; if(now == B[to] - A[to] + G[v][i].second) now = mx2; dfs(to, max(tot - A[to], now + tot - A[to] + G[v][i].second), tot - A[to]); } } int main() { scanf("%d", &n); for(int i = 1; i < n; ++ i) { int x, y, val; scanf("%d %d %d", &x, &y, &val); G[x].push_back({y, val}); G[y].push_back({x, val}); } par[1] = -2e9; go(1); dfs(1, 0, 0); cout << answer << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 6 ms | 5120 KB | Output is correct |
4 | Correct | 5 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 5120 KB | Output is correct |
6 | Correct | 6 ms | 5120 KB | Output is correct |
7 | Correct | 5 ms | 5120 KB | Output is correct |
8 | Correct | 6 ms | 5120 KB | Output is correct |
9 | Correct | 5 ms | 5120 KB | Output is correct |
10 | Correct | 6 ms | 4992 KB | Output is correct |
11 | Correct | 6 ms | 5120 KB | Output is correct |
12 | Correct | 5 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 6 ms | 5120 KB | Output is correct |
4 | Correct | 5 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 5120 KB | Output is correct |
6 | Correct | 6 ms | 5120 KB | Output is correct |
7 | Correct | 5 ms | 5120 KB | Output is correct |
8 | Correct | 6 ms | 5120 KB | Output is correct |
9 | Correct | 5 ms | 5120 KB | Output is correct |
10 | Correct | 6 ms | 4992 KB | Output is correct |
11 | Correct | 6 ms | 5120 KB | Output is correct |
12 | Correct | 5 ms | 4992 KB | Output is correct |
13 | Correct | 6 ms | 4992 KB | Output is correct |
14 | Correct | 7 ms | 5120 KB | Output is correct |
15 | Correct | 6 ms | 4992 KB | Output is correct |
16 | Correct | 6 ms | 5120 KB | Output is correct |
17 | Correct | 6 ms | 4992 KB | Output is correct |
18 | Correct | 16 ms | 4992 KB | Output is correct |
19 | Correct | 7 ms | 5120 KB | Output is correct |
20 | Correct | 6 ms | 5120 KB | Output is correct |
21 | Correct | 14 ms | 5120 KB | Output is correct |
22 | Correct | 6 ms | 4992 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 6 ms | 5120 KB | Output is correct |
4 | Correct | 5 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 5120 KB | Output is correct |
6 | Correct | 6 ms | 5120 KB | Output is correct |
7 | Correct | 5 ms | 5120 KB | Output is correct |
8 | Correct | 6 ms | 5120 KB | Output is correct |
9 | Correct | 5 ms | 5120 KB | Output is correct |
10 | Correct | 6 ms | 4992 KB | Output is correct |
11 | Correct | 6 ms | 5120 KB | Output is correct |
12 | Correct | 5 ms | 4992 KB | Output is correct |
13 | Correct | 6 ms | 4992 KB | Output is correct |
14 | Correct | 7 ms | 5120 KB | Output is correct |
15 | Correct | 6 ms | 4992 KB | Output is correct |
16 | Correct | 6 ms | 5120 KB | Output is correct |
17 | Correct | 6 ms | 4992 KB | Output is correct |
18 | Correct | 16 ms | 4992 KB | Output is correct |
19 | Correct | 7 ms | 5120 KB | Output is correct |
20 | Correct | 6 ms | 5120 KB | Output is correct |
21 | Correct | 14 ms | 5120 KB | Output is correct |
22 | Correct | 6 ms | 4992 KB | Output is correct |
23 | Correct | 9 ms | 5376 KB | Output is correct |
24 | Correct | 9 ms | 5376 KB | Output is correct |
25 | Correct | 8 ms | 5376 KB | Output is correct |
26 | Correct | 12 ms | 5632 KB | Output is correct |
27 | Correct | 13 ms | 5632 KB | Output is correct |
28 | Correct | 11 ms | 5760 KB | Output is correct |
29 | Correct | 11 ms | 5632 KB | Output is correct |
30 | Correct | 11 ms | 5632 KB | Output is correct |
31 | Correct | 12 ms | 5888 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5120 KB | Output is correct |
2 | Correct | 6 ms | 5120 KB | Output is correct |
3 | Correct | 6 ms | 5120 KB | Output is correct |
4 | Correct | 5 ms | 5120 KB | Output is correct |
5 | Correct | 7 ms | 5120 KB | Output is correct |
6 | Correct | 6 ms | 5120 KB | Output is correct |
7 | Correct | 5 ms | 5120 KB | Output is correct |
8 | Correct | 6 ms | 5120 KB | Output is correct |
9 | Correct | 5 ms | 5120 KB | Output is correct |
10 | Correct | 6 ms | 4992 KB | Output is correct |
11 | Correct | 6 ms | 5120 KB | Output is correct |
12 | Correct | 5 ms | 4992 KB | Output is correct |
13 | Correct | 6 ms | 4992 KB | Output is correct |
14 | Correct | 7 ms | 5120 KB | Output is correct |
15 | Correct | 6 ms | 4992 KB | Output is correct |
16 | Correct | 6 ms | 5120 KB | Output is correct |
17 | Correct | 6 ms | 4992 KB | Output is correct |
18 | Correct | 16 ms | 4992 KB | Output is correct |
19 | Correct | 7 ms | 5120 KB | Output is correct |
20 | Correct | 6 ms | 5120 KB | Output is correct |
21 | Correct | 14 ms | 5120 KB | Output is correct |
22 | Correct | 6 ms | 4992 KB | Output is correct |
23 | Correct | 9 ms | 5376 KB | Output is correct |
24 | Correct | 9 ms | 5376 KB | Output is correct |
25 | Correct | 8 ms | 5376 KB | Output is correct |
26 | Correct | 12 ms | 5632 KB | Output is correct |
27 | Correct | 13 ms | 5632 KB | Output is correct |
28 | Correct | 11 ms | 5760 KB | Output is correct |
29 | Correct | 11 ms | 5632 KB | Output is correct |
30 | Correct | 11 ms | 5632 KB | Output is correct |
31 | Correct | 12 ms | 5888 KB | Output is correct |
32 | Correct | 41 ms | 8056 KB | Output is correct |
33 | Correct | 38 ms | 8056 KB | Output is correct |
34 | Correct | 41 ms | 8184 KB | Output is correct |
35 | Correct | 235 ms | 17144 KB | Output is correct |
36 | Correct | 259 ms | 17272 KB | Output is correct |
37 | Correct | 268 ms | 17400 KB | Output is correct |
38 | Correct | 193 ms | 17508 KB | Output is correct |
39 | Correct | 178 ms | 17612 KB | Output is correct |
40 | Correct | 182 ms | 17528 KB | Output is correct |
41 | Correct | 242 ms | 20400 KB | Output is correct |