Submission #699109

#TimeUsernameProblemLanguageResultExecution timeMemory
699109Ronin13Beads and wires (APIO14_beads)C++14
0 / 100
7 ms11988 KiB
#include <bits/stdc++.h> #define ll long long #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int nmax =500001; /* 10 4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34 */ ll dp[nmax][2][2]; ll val[nmax]; vector <vector <pii> > g(nmax); void dfs(int v, int e = -1){ ll mx = -1e9; pair<pll, pll> mx1; pair<pll, pll> mx2; pair<pll, pll> mx3, mx4; mx1 = mx2 = mx3 = mx4 = {{mx, mx}, {mx, mx}}; ll MX = -1e9; for(auto ed : g[v]){ int to = ed.f; ll len = ed.s; if(to == e) continue; val[to] = len; dfs(to, v); ll y = max(dp[to][1][0], dp[to][0][0]); dp[v][0][0] += y; mx = max(mx, dp[to][0][0] - y + val[to]); ll z = dp[to][0][1] - y + val[to]; mx1.s = max(mx1.s, {z, to}); if(mx1.f < mx1.s) swap(mx1.f, mx1.s); z = dp[to][0][0] - y + val[to]; mx2.s = max(mx2.s, {z, to}); if(mx2.f < mx2.s) swap(mx2.f, mx2.s); MX = max(MX, dp[to][0][1] - y + val[to]); } dp[v][1][0] = max(dp[v][1][0], mx + dp[v][0][0] + val[v]); if(mx1.f.s == mx2.f.s){ dp[v][0][1] = dp[v][0][0] + max(mx1.f.f + mx2.s.f, mx1.s.f + mx2.f.f); } else dp[v][0][1] = max(dp[v][0][1], dp[v][0][0] + mx1.f.f + mx2.f.f); dp[v][1][1] = dp[v][0][0] + MX + val[v]; dp[v][0][1] = max(dp[v][0][1], dp[v][0][0]); dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]); } int32_t main() { int n; cin >> n; val[1] = -1e9; for(int i = 1; i < n; i++){ int u, v, c; cin >> u >> v >> c; g[u].pb({v, c}); g[v].pb({u, c}); } dfs(1); cout << max(dp[1][0][1], dp[1][0][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...