Submission #1202742

#TimeUsernameProblemLanguageResultExecution timeMemory
1202742Zbyszek99Beads and wires (APIO14_beads)C++20
100 / 100
69 ms17848 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vector<pii> graph[200001]; int dp[200001][2]; int ans = 0; void dfs(int v, int pop, int pop_edge) { int sum = 0; int best_son = -5e8; forall(it,graph[v]) { if(it.ff != pop) { dfs(it.ff,v,it.ss); sum += max(dp[it.ff][0],dp[it.ff][1]); best_son = max(best_son,dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1])); } } dp[v][0] = sum; dp[v][1] = sum + best_son + pop_edge; } void dfs_ans(int v, int pop) { int old_dp0 = dp[v][0]; int old_dp1 = dp[v][1]; int sum = 0; pii best_son = {-5e8,-5e8}; forall(it,graph[v]) { sum += max(dp[it.ff][0],dp[it.ff][1]); if(best_son.ff < dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1])) { best_son.ss = best_son.ff; best_son.ff = dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1]); } else if(best_son.ss < dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1])) { best_son.ss = dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1]); } } // cout << v << " " << sum << " " << best_son.ff << " " << best_son.ss << " dfs\n"; ans = max(ans,sum); forall(it,graph[v]) { if(it.ff != pop) { dp[v][0] = sum - max(dp[it.ff][0],dp[it.ff][1]); int b = best_son.ff; if(b == dp[it.ff][0] + it.ss - max(dp[it.ff][0],dp[it.ff][1])) b = best_son.ss; dp[v][1] = sum + b + it.ss - max(dp[it.ff][0],dp[it.ff][1]); dfs_ans(it.ff,v); } } dp[v][0] = old_dp0; dp[v][1] = old_dp1; } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n; cin >> n; rep(i,n-1) { int a,b,c; cin >> a >> b >> c; graph[a].pb({b,c}); graph[b].pb({a,c}); } dfs(1,1,0); dfs_ans(1,1); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...