Submission #538831

#TimeUsernameProblemLanguageResultExecution timeMemory
538831LoboBeads and wires (APIO14_beads)C++17
100 / 100
209 ms29576 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() #define maxn 200020 int n, dp[maxn][2], ans; pair<int,int> mxv[maxn]; vector<pair<int,int>> g[maxn]; // dp(u,1) ta com azul pro pai e vai ter qual o melhor pra continuar assim // void dfs(int u, int p) { int ans1 = 0; mxv[u] = mp(-inf,-inf); for(auto V : g[u]) { int v = V.fr; int w = V.sc; if(v == p) continue; dfs(v,u); ans1+= max(dp[v][0],dp[v][1]+w); mxv[u].sc = max(mxv[u].sc, dp[v][0] + w - max(dp[v][0],dp[v][1]+w)); if(mxv[u].sc > mxv[u].fr) swap(mxv[u].fr,mxv[u].sc); } dp[u][0] = ans1; dp[u][1] = ans1+mxv[u].fr; // cout << u << " -- " << dp[u][0] << " " << dp[u][1] << endl; } void reroot(int u, int p, int wp) { //p é a raiz da tree até entao //tiro o u do p e insiro o p no u int antu0 = dp[u][0]; int antu1 = dp[u][1]; int antp0 = dp[p][0]; int antp1 = dp[p][1]; pair<int,int> antmxv = mxv[u]; //tirar u do p dp[p][0]-= max(dp[u][0],dp[u][1]+wp); if(mxv[p].fr == dp[u][0] + wp - max(dp[u][0],dp[u][1]+wp)) dp[p][1] = dp[p][0]+mxv[p].sc; else dp[p][1] = dp[p][0] + mxv[p].fr; //insiro p em u dp[u][0]+= max(dp[p][0],dp[p][1]+wp); mxv[u].sc = max(mxv[u].sc, dp[p][0] + wp - max(dp[p][0],dp[p][1]+wp)); if(mxv[u].sc > mxv[u].fr) swap(mxv[u].fr,mxv[u].sc); dp[u][1] = dp[u][0] + mxv[u].fr; ans = max(ans, dp[u][0]); for(auto V : g[u]) { int v = V.fr; int w = V.sc; if(v == p) continue; reroot(v,u,w); } //volta as respostas anteriores dp[u][0] = antu0; dp[u][1] = antu1; dp[p][0] = antp0; dp[p][1] = antp1; mxv[u] = antmxv; } void solve() { cin >> n; for(int i = 1; i < n; i++) { int u,v,w; cin >> u >> v >> w; g[u].pb(mp(v,w)); g[v].pb(mp(u,w)); } dfs(1,1); ans = dp[1][0]; for(auto V : g[1]) { int v = V.fr; int w = V.sc; reroot(v,1,w); } cout << ans << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...