# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883274 | 2023-12-05T02:59:16 Z | nguyentunglam | Beads and wires (APIO14_beads) | C++17 | 1000 ms | 3416 KB |
#include<bits/stdc++.h> #define all(v) v.begin(), v.end() #define endl "\n" using namespace std; const int N = 1e5 + 10; int f[N], g[N]; vector<pair<int, int> > adj[N]; void dfs(int u, int p) { int sum = 0, maxw = -1e9; bool leaf = 1; for(auto &[v, w] : adj[u]) if (v != p) { dfs(v, u); leaf = 0; int h = max(f[v], g[v] + w); sum += h; maxw = max(maxw, w + f[v] - h); } if (leaf) { f[u] = 0; g[u] = -1e9; } g[u] = sum + maxw; f[u] = sum; } int32_t main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen("task.inp", "r")) { freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); } if (fopen(task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } int n; cin >> n; for(int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; adj[a].emplace_back(b, c); adj[b].emplace_back(a, c); } int ans = 0; for(int i = 1; i <= n; i++) { dfs(i, 0); ans = max(ans, f[i]); } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
2 | Correct | 2 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 1 ms | 2812 KB | Output is correct |
8 | Correct | 1 ms | 2648 KB | Output is correct |
9 | Correct | 1 ms | 2652 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
2 | Correct | 2 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 1 ms | 2812 KB | Output is correct |
8 | Correct | 1 ms | 2648 KB | Output is correct |
9 | Correct | 1 ms | 2652 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2652 KB | Output is correct |
13 | Correct | 1 ms | 2648 KB | Output is correct |
14 | Correct | 1 ms | 2812 KB | Output is correct |
15 | Correct | 1 ms | 2652 KB | Output is correct |
16 | Correct | 1 ms | 2648 KB | Output is correct |
17 | Correct | 1 ms | 2652 KB | Output is correct |
18 | Correct | 1 ms | 2816 KB | Output is correct |
19 | Correct | 1 ms | 2652 KB | Output is correct |
20 | Correct | 1 ms | 2652 KB | Output is correct |
21 | Correct | 1 ms | 2652 KB | Output is correct |
22 | Correct | 1 ms | 2652 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
2 | Correct | 2 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 1 ms | 2812 KB | Output is correct |
8 | Correct | 1 ms | 2648 KB | Output is correct |
9 | Correct | 1 ms | 2652 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2652 KB | Output is correct |
13 | Correct | 1 ms | 2648 KB | Output is correct |
14 | Correct | 1 ms | 2812 KB | Output is correct |
15 | Correct | 1 ms | 2652 KB | Output is correct |
16 | Correct | 1 ms | 2648 KB | Output is correct |
17 | Correct | 1 ms | 2652 KB | Output is correct |
18 | Correct | 1 ms | 2816 KB | Output is correct |
19 | Correct | 1 ms | 2652 KB | Output is correct |
20 | Correct | 1 ms | 2652 KB | Output is correct |
21 | Correct | 1 ms | 2652 KB | Output is correct |
22 | Correct | 1 ms | 2652 KB | Output is correct |
23 | Correct | 358 ms | 3084 KB | Output is correct |
24 | Correct | 343 ms | 3416 KB | Output is correct |
25 | Correct | 355 ms | 3088 KB | Output is correct |
26 | Execution timed out | 1061 ms | 3164 KB | Time limit exceeded |
27 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
2 | Correct | 2 ms | 2652 KB | Output is correct |
3 | Correct | 1 ms | 2652 KB | Output is correct |
4 | Correct | 1 ms | 2652 KB | Output is correct |
5 | Correct | 1 ms | 2652 KB | Output is correct |
6 | Correct | 1 ms | 2652 KB | Output is correct |
7 | Correct | 1 ms | 2812 KB | Output is correct |
8 | Correct | 1 ms | 2648 KB | Output is correct |
9 | Correct | 1 ms | 2652 KB | Output is correct |
10 | Correct | 1 ms | 2652 KB | Output is correct |
11 | Correct | 1 ms | 2652 KB | Output is correct |
12 | Correct | 1 ms | 2652 KB | Output is correct |
13 | Correct | 1 ms | 2648 KB | Output is correct |
14 | Correct | 1 ms | 2812 KB | Output is correct |
15 | Correct | 1 ms | 2652 KB | Output is correct |
16 | Correct | 1 ms | 2648 KB | Output is correct |
17 | Correct | 1 ms | 2652 KB | Output is correct |
18 | Correct | 1 ms | 2816 KB | Output is correct |
19 | Correct | 1 ms | 2652 KB | Output is correct |
20 | Correct | 1 ms | 2652 KB | Output is correct |
21 | Correct | 1 ms | 2652 KB | Output is correct |
22 | Correct | 1 ms | 2652 KB | Output is correct |
23 | Correct | 358 ms | 3084 KB | Output is correct |
24 | Correct | 343 ms | 3416 KB | Output is correct |
25 | Correct | 355 ms | 3088 KB | Output is correct |
26 | Execution timed out | 1061 ms | 3164 KB | Time limit exceeded |
27 | Halted | 0 ms | 0 KB | - |