Submission #722571

#TimeUsernameProblemLanguageResultExecution timeMemory
722571stevancvBeads and wires (APIO14_beads)C++14
0 / 100
3 ms4988 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define sp ' ' #define en '\n' #define smin(a, b) a = min(a, b) #define smax(a, b) a = max(a, b) using namespace std; const int N = 2e5 + 2; const int inf = 1e9; vector<pair<int, int>> g[N]; int dp[N][2]; void Dfs(int s, int e, int val) { int sum = 0; int mx = -inf; for (auto z : g[s]) { int u = z.first; int v = z.second; if (u == e) continue; Dfs(u, s, v); sum += max(dp[u][0], dp[u][1]); smax(mx, dp[u][0] + v + val - max(dp[u][0], dp[u][1])); } dp[s][0] = sum; dp[s][1] = sum + mx; } int sol, up[N][2]; void Dfs1(int s, int e, int val) { smax(sol, max(up[s][0], up[s][1]) + dp[s][0]); int x, y; x = y = -inf; for (auto z : g[s]) { int u = z.first; int v = z.second; if (u == e) continue; int o = dp[u][0] + v - max(dp[u][0], dp[u][1]); if (o > x) y = x, x = o; else if (o > y) y = o; } for (auto z : g[s]) { int u = z.first; int v = z.second; if (u == e) continue; int uk = dp[s][0] - max(dp[u][0], dp[u][1]); if (s > 1) up[u][1] = up[u][0] + val + v + uk; int o = dp[u][0] + v - max(dp[u][0], dp[u][1]); int kolko = x; if (o == x) kolko = y; smax(up[u][1], v + uk + kolko + max(up[s][0], up[s][1])); up[u][0] = max(up[s][0], up[s][1]) + uk; Dfs1(u, s, v); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back({v, w}); g[v].push_back({u, w}); } Dfs(1, 0, 0); Dfs1(1, 0, 0); cout << sol << en; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...