Submission #725302

#TimeUsernameProblemLanguageResultExecution timeMemory
725302quiet_spaceBeads and wires (APIO14_beads)C++14
100 / 100
193 ms51924 KiB
#include <bits/stdc++.h> #define FOR(i,j,k) for(int i=j; i<=k; ++i) #define ROF(i,j,k) for(int i=j; i>=k; --i) inline int read (void) { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) { if(ch == '-') f = -f; ch = getchar(); } while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } const int maxn = 200005; int tot_edge, head[maxn], to[maxn<<1], link[maxn<<1], cost[maxn<<1]; inline void add_edge (int x, int y, int c) { to[++tot_edge] = y; cost[tot_edge] = c; link[tot_edge] = head[x]; head[x] = tot_edge; } int fa[maxn], len[maxn], f[maxn][2]; std::vector <int> v[maxn], dp[maxn][2], mx[maxn]; void dfs (int x, int Fa=0) { f[x][1] = -1 << 30; int mx1 = -1 << 30, mx2 = -1 << 30; for(int now=head[x]; now; now=link[now]) { if(to[now] == Fa) continue; fa[to[now]] = x; len[to[now]] = cost[now]; v[x].push_back (to[now]); dfs (to[now], x); f[x][0] += std::max(f[to[now]][0], f[to[now]][1] + cost[now]); int v = f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]); if(v > mx1) mx2 = mx1, mx1 = v; else if(v > mx2) mx2 = v; } f[x][1] = f[x][0] + mx1; for(int now=head[x]; now; now=link[now]) { if(to[now] == Fa) continue; dp[x][0].push_back (f[x][0] - std::max(f[to[now]][0], f[to[now]][1] + cost[now])); if(f[to[now]][0] + cost[now] - std::max(f[to[now]][0], f[to[now]][1] + cost[now]) == mx1) dp[x][1].push_back (dp[x][0].back() + mx2), mx[x].push_back (mx2); else dp[x][1].push_back (dp[x][0].back() + mx1), mx[x].push_back (mx1); } } int ans; void solve (int x) { int s = v[x].size(); FOR(i,0,s-1) { f[x][0] = dp[x][0][i], f[x][1] = dp[x][1][i]; if(fa[x]) { f[x][0] += std::max(f[fa[x]][0], f[fa[x]][1] + len[x]); f[x][1] = f[x][0] + std::max(mx[x][i], f[fa[x]][0] + len[x] - std::max(f[fa[x]][0], f[fa[x]][1] + len[x])); } ans = std::max(ans, f[v[x][i]][0] + std::max(f[x][0], f[x][1] + len[v[x][i]])); solve (v[x][i]); } } int main (void) { int n = read(); FOR(i,2,n) { int x = read(), y = read(), c = read(); add_edge (x, y, c); add_edge (y, x, c); } dfs (1); solve (1); printf("%d\n", ans); 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...