제출 #1202603

#제출 시각아이디문제언어결과실행 시간메모리
1202603niepamietamhaslaBeads and wires (APIO14_beads)C++20
100 / 100
75 ms20476 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 5; const int MAXINT = 2e9; vector<pair<int,int>> graf[MAXN]; int dp[MAXN][2]; pair<int,int> gdz[MAXN][2]; int ans = 0; int dfs1(int v, int p){ int m = -MAXINT; for(auto u : graf[v]){ if(u.first == p) continue; dfs1(u.first, v); dp[v][0] += max(dp[u.first][0], dp[u.first][1] + u.second); m = max(m, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second)); } dp[v][1] = dp[v][0] + m; return 0; } void dfs2(int v, int p, int k){ int m1, m2; int k1, k2; m1 = m2 = k1 = k2 = -MAXINT; if(v != 1){ int w1, w2; w1 = dp[p][0] - max(dp[v][0], dp[v][1] + k); if(gdz[p][0].first == v){ w2 = w1 + gdz[p][1].second; } else{ w2 = w1 + gdz[p][0].second; } int ma = w1 + k - max(w1, w2 + k); for(auto u : graf[v]){ if(u.first == p) continue; ma = max(ma, dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second)); } m1 = w1 + k - max(w1, w2 + k); k1 = p; dp[v][0] += max(w1, w2 + k); dp[v][1] += max(w1, w2 + k) + ma; } for(auto u : graf[v]){ if(u.first == p) continue; int c = dp[u.first][0] + u.second - max(dp[u.first][0], dp[u.first][1] + u.second); if(c > m1){ m2 = m1; m1 = c; k2 = k1; k1 = u.first; } else if(c > m2){ m2 = c; k2 = u.first; } } ans = max(ans, dp[v][0]); gdz[v][0] = {k1, m1}; gdz[v][1] = {k2, m2}; for(auto u : graf[v]){ if(u.first == p) continue; dfs2(u.first, v, u.second); } return; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int a, b, c; for(int i = 0; i < n-1; ++i){ cin >> a >> b >> c; graf[a].push_back({b,c}); graf[b].push_back({a,c}); } dfs1(1, -1); ans = dp[1][0]; dfs2(1, -1, 0); cout << ans << "\n"; 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...