제출 #1002371

#제출 시각아이디문제언어결과실행 시간메모리
1002371GrindMachine구슬과 끈 (APIO14_beads)C++17
100 / 100
165 ms40000 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* read some solution ideas, found them non-intuitive trying to build upon my previous idea */ const int MOD = 1e9 + 7; const int N = 2e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; struct S : vector<int>{ int shift = 0; int operator[](int i){ return at(i)+shift; } void point_set(int i, int v){ at(i) = v-shift; } void point_add(int i, int v){ at(i) += v; } void do_shift(int x){ shift += x; } }; vector<pii> adj[N]; S dp[N]; vector<int> best(N,-inf1); void dfs1(ll u, ll p){ for(auto [v,w] : adj[u]){ if(v == p) conts; dfs1(v,u); } // dp[u][0] = 0; int sum = 0; rep(i,sz(adj[u])){ auto [v,w] = adj[u][i]; if(v == p) conts; int curr_val = max(w+best[v],dp[v][0]); sum += curr_val; dp[u].point_set(i+1,-curr_val); // dp[u][0] += curr_val; // dp[u][i+1] = -curr_val; } rep(i,sz(adj[u])+1){ dp[u].point_add(i,sum); // dp[u][i] += dp[u][0]; } best[u] = -inf1; rep(j,sz(adj[u])){ auto [v,w] = adj[u][j]; if(v == p) conts; amax(best[u],w+dp[u][j+1]+dp[v][0]); } } int ans = 0; void dfs2(int u, int p){ amax(ans,dp[u][0]); // debug(u,dp[u][0]); vector<pii> vals; rep(j,sz(adj[u])){ auto [v2,w2] = adj[u][j]; int val = w2+dp[u][j+1]+dp[v2][0]; vals.pb({val,v2}); } sort(rall(vals)); while(sz(vals) > 2){ vals.pop_back(); } rep(i,sz(adj[u])){ auto [v,w] = adj[u][i]; if(v == p) conts; int id = -1; rep(j,sz(adj[v])){ auto [v2,w2] = adj[v][j]; if(v2 == u){ id = j+1; break; } } int contrib = max(w+best[v],dp[v][0]); dp[u].point_add(i+1,contrib); dp[u].do_shift(-contrib); // dp[u][i+1] += contrib; // rep(j,sz(adj[u])+1){ // dp[u][j] -= contrib; // } int add = 0; for(auto [val,v2] : vals){ if(v2 == v) conts; amax(add,w+val-contrib); } // rep(j,sz(adj[u])){ // if(j == i) conts; // auto [v2,w2] = adj[u][j]; // int val = w+w2+dp[u][j+1]+dp[v2][0]; // amax(add,val); // } amax(add,dp[u][0]); dp[v].point_add(id,-add); // dp[v][id] -= add; rep(j,sz(adj[v])+1){ dp[v].point_add(j,add); // dp[v][j] += add; } dfs2(v,u); dp[u].do_shift(contrib); dp[u].point_add(i+1,-contrib); // rep(j,sz(adj[u])+1){ // dp[u][j] += contrib; // } // dp[u][i+1] -= contrib; rep(j,sz(adj[v])+1){ dp[v].point_add(j,-add); // dp[v][j] -= add; } dp[v].point_add(id,add); // dp[v][id] += add; } } void solve(int test_case) { int n; cin >> n; rep1(i,n-1){ int u,v,c; cin >> u >> v >> c; adj[u].pb({v,c}), adj[v].pb({u,c}); } rep1(u,n){ dp[u].resize(sz(adj[u])+1); } dfs1(1,-1); dfs2(1,-1); cout << ans << endl; // int oans = 0; // rep1(i,n){ // dfs1(i,-1); // amax(oans,dp[i][0]); // debug(dp[i][0]); // } // assert(ans == oans); } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } 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...