제출 #1163795

#제출 시각아이디문제언어결과실행 시간메모리
1163795byunjaewooBeads and wires (APIO14_beads)C++20
0 / 100
2 ms4936 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, sum=0, mx3=-INF, mx4=-INF, mx5=-INF; vector<int> vec; for(auto [next, w]:adj[curr]) if(next!=prev) { pw[next]=w, dfs(next, curr); dp[0][curr]+=max(dp[0][next], ep[0][next]); ep[0][curr]+=max(dp[0][next], ep[0][next]); if(dp[0][next]>=ep[0][next]) mx1=max(mx1, w); else mx1=max(mx1, dp[0][next]+w-ep[0][next]); ep[1][curr]+=max({dp[0][next], dp[1][next], ep[0][next], ep[1][next]}); if(max(dp[0][next], dp[1][next])>=ep[0][next]) mx2=max(mx2, w); else mx2=max(mx2, max(dp[0][next], dp[1][next])+w-max(ep[0][next], ep[1][next])); sum+=max(dp[0][next], ep[0][next]); if(dp[0][next]>=ep[0][next]) { if(mx3<w) mx4=mx3, mx3=w; else if(mx4<w) mx4=w; } else { if(mx3<dp[0][next]+w-ep[0][next]) mx4=mx3, mx3=dp[0][next]+w-ep[0][next]; else if(mx4<dp[0][next]+w-ep[0][next]) mx4=dp[0][next]+w-ep[0][next]; } vec.push_back(mx3); } ep[0][curr]+=mx1+pw[curr], ep[1][curr]+=mx2+pw[curr]; dp[1][curr]=sum+mx3+mx4; 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(mx5, p?vec[--p]:-INF)); if(dp[0][next]>=ep[0][next]) mx5=max(mx5, w); else mx5=max(mx5, dp[0][next]+w-ep[0][next]); } } 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...