Submission #1159136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159136		mertbbm	Beads and wires (APIO14_beads)	C++20	100 / 100	250 ms	41244 KiB

beads

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<pii>adj[200005];

int dp[200005][3];

void dfs(int index, int par, int len){
	int counter=0;
	int change=-1e15;
	for(auto it:adj[index]){
		if(it.first==par) continue;
		dfs(it.first,index,it.second);
		int hold=max(dp[it.first][0],dp[it.first][2]);
		change=max(change,dp[it.first][1]-hold);
		counter+=hold;
	}
	dp[index][0]=counter;
	dp[index][2]=counter+change+len;
	dp[index][1]=counter+len;
}

int best=0;

void dfs2(int index, int par, int len){
	//compute answer
	int counter=0;
	multiset<pii>se;
	for(auto it:adj[index]){
		int hold=max(dp[it.first][0],dp[it.first][2]);
		int change=dp[it.first][1]-hold;
		se.insert({change,it.first});
		counter+=hold;
	}
	//show2(index,index,counter,counter);
	best=max(best,counter);
	
	array<int,3>undo={dp[index][0],dp[index][1],dp[index][2]};
	se.insert({-1e15,0});
	for(auto it:adj[index]){
		if(it.first==par) continue;
		int hold=max(dp[it.first][0],dp[it.first][2]);
		int change=dp[it.first][1]-hold;
		se.erase(se.find({change,it.first}));
		dp[index][0]=counter-hold;
		dp[index][2]=counter-hold+prev(se.end())->first+it.second;
		dp[index][1]=counter-hold+it.second;
		//cout << index << " " << it.first << " " << dp[index][0] << " " << dp[index][1] << " " << dp[index][2] << "\n";
		dfs2(it.first,index,it.second);
		dp[index][0]=undo[0];
		dp[index][1]=undo[1];
		dp[index][2]=undo[2];
		se.insert({change,it.first});
	}
}

void solve(){
	int n;
	cin >> n;
	
	int temp,temp2,temp3;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2 >> temp3;
		adj[temp].push_back({temp2,temp3});
		adj[temp2].push_back({temp,temp3});
	}
	
	dfs(1,-1,0);
	
	//reroot
	dfs2(1,-1,0);
	cout << best;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("in.txt","w",stdout);
	int t=1;	        
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43