Submission #1014073

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014073		peacebringer1667	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	4956 KiB

beads

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair <int,int>
using namespace std;
const int maxn = 2e5 + 5;
const int alp = 2;
const ll inf = 1e16;

vector <vector<pir>> vec(maxn);
ll dp[maxn][alp];

void purge_par(int u,int par){
	int vt = -1;
	for (int i = 0 ; i < vec[u].size() ; i++)
	  if (vec[u][i].fi == par){
	  	 vt = i;
	  	 break;
	  }
	if (vt != -1){
		swap(vec[u][vec[u].size() - 1],vec[u][vt]);
		vec[u].pop_back();
	}
}
void dfs_prepare(int u,int par){
	purge_par(u,par);

	for (pair <int,int> v : vec[u])
	  dfs_prepare(v.fi,u);
}

void get_dp(int u){
  if (vec[u].size() >= 2){
	ll M1 = -inf,M2 = -inf;
	ll T = 0;
	for (pir v : vec[u]){
		
		ll V = dp[v.fi][0];
		if (dp[v.fi][1] != -1)
		  V = max(V,dp[v.fi][1] + v.se);
		  
		T += V;
		ll val = v.se + dp[v.fi][0] - V;
		if (M1 <= val){
			M2 = M1;
			M1 = val;
		}
		else
		  M2 = max(M2,val);
	}
	
	dp[u][0] = max(dp[u][0],T);
	dp[u][0] = max(dp[u][0],T + M1 + M2);
  }
  else{
  	pir v = vec[u][0];
  	
  	dp[u][0] = dp[v.fi][0];
    if (dp[v.fi][1] != -1)
       dp[u][0] = max(dp[u][0],dp[v.fi][1] + v.se);
   }
}

void get_extra_dp(int u){
	int N = vec[u].size();
	
	// 2 already down
	vector <ll> pre(N + 3);
	for (int i = 1 ; i <= N ; i++){
	   pir v = vec[u][i - 1];
	   
	   pre[i] = pre[i - 1] + dp[v.fi][0];
	   
	   if (dp[v.fi][1] != -1)
	     pre[i] = max(pre[i],pre[i - 1] + dp[v.fi][1] + v.se);
	}
	ll T = 0;
	for (int i = 1 ; i <= N ; i++){
		pir v = vec[u][i - 1];
		T = max(T,v.se + pre[i - 1] + pre[N] - pre[i] + dp[v.fi][0]);
	}
	
	dp[u][1] = max(dp[u][1],T);
}

void dfs(int u){
	if (!vec[u].size()){
		dp[u][1] = -1;
		return;
	}
	
	for (pir v : vec[u])
		dfs(v.fi);
	
	get_dp(u);
	get_extra_dp(u);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    
   // freopen("beads.in","r",stdin);
  //  freopen("beads.out","w",stdout);
    
    int n;
    cin >> n;
    for (int i = 1 ; i < n ; i++){
    	int u,v,w;
    	cin >> u >> v >> w;
    	vec[u].push_back({v,w});
    	vec[v].push_back({u,w});
	}
	
	dfs_prepare(1,-1);
	dfs(1);
	
	cout << dp[1][0] << "\n";
    
	return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void purge_par(int, int)':
beads.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int i = 0 ; i < vec[u].size() ; i++)
      |                   ~~^~~~~~~~~~~~~~~

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