Submission #1163837

#TimeUsernameProblemLanguageResultExecution timeMemory
1163837byunjaewooBeads and wires (APIO14_beads)C++20
100 / 100
87 ms31484 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=200010, INF=1e15; int n, pw[N], dp[2][N], ep[2][N]; vector<pair<int, int>> adj[N]; void dfs(int curr, int prev) { int mx1=-INF, mx2=-INF, mx3=-INF, mx4=-INF, mx5=-INF, sum=0; vector<int> vec; for(auto [next, w]:adj[curr]) if(next!=prev) { pw[next]=w, dfs(next, curr); sum+=max(dp[0][next], ep[0][next]); if(dp[0][next]>=ep[0][next]) { if(mx1<w) mx2=mx1, mx1=w; else if(mx2<w) mx2=w; } else { if(mx1<dp[0][next]+w-ep[0][next]) mx2=mx1, mx1=dp[0][next]+w-ep[0][next]; else if(mx2<dp[0][next]+w-ep[0][next]) mx2=dp[0][next]+w-ep[0][next]; } vec.push_back(mx1); } dp[0][curr]=sum, ep[0][curr]=sum+mx1+pw[curr], ep[1][curr]=sum+mx1+pw[curr], dp[1][curr]=max(sum, sum+mx1+mx2); reverse(adj[curr].begin(), adj[curr].end()); int p=vec.size()-1; for(auto [next, w]:adj[curr]) if(next!=prev) { dp[1][curr]=max(dp[1][curr], sum-max(dp[0][next], ep[0][next])+dp[1][next]+w+max(mx3, p?vec[--p]:-INF)); dp[1][curr]=max(dp[1][curr], sum-max(dp[0][next], ep[0][next])+max(dp[1][next], ep[1][next])); if(dp[0][next]>=ep[0][next]) mx3=max(mx3, w); else mx3=max(mx3, dp[0][next]+w-ep[0][next]); } p=vec.size()-1; for(auto [next, w]:adj[curr]) if(next!=prev) { ep[1][curr]=max(ep[1][curr], sum-max(dp[0][next], ep[0][next])+dp[1][next]+w+pw[curr]); } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; for(int i=1; i<n; i++) { int u, v, w; cin>>u>>v>>w; adj[u].push_back({v, w}), adj[v].push_back({u, w}); } dfs(1, 0); cout<<max(dp[0][1], dp[1][1]); 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...