Submission #162221

#	Time	Username	Problem	Language	Result	Execution time	Memory
162221		HungAnhGoldIBO2020	Beads and wires (APIO14_beads)	C++14	0 / 100	7 ms	5112 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
const int inf=1e9+7;
vector<pair<int,int> > adj[N];
int dp[N][2][2][2];
void dfs(int x,int p,int val){
	int sum=0,sum1=0,max1=-inf,max2=-inf,max3=-inf;
	for(auto j:adj[x]){
		int i=j.first;
		if(i!=p){
			dfs(i,x,j.second);
			dp[x][0][0][0]+=max(dp[i][0][0][0],dp[i][1][1][0]);
			if(max1<max(dp[i][0][0][1],dp[i][1][0][1])-max(dp[i][0][0][0],dp[i][1][1][0])){
				max1=max(dp[i][0][0][1],dp[i][1][0][1])-max(dp[i][0][0][0],dp[i][1][1][0]);
			}
			//for 0,0,1
			if(max2<=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
				max3=max2;
				max2=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
			}
			else{
				if(max3<max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
					max3=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
				}
			}
			//for both 1,0,1 and 1,1,0
		}
	}
//	if(x==1){
//		cout<<max1<<' '<<max2<<' '<<max3<<endl;
//	}
	dp[x][0][0][1]=max(0,dp[x][0][0][0]+max1);
	dp[x][1][1][0]=max(0,dp[x][0][0][0]+max2+val);
	dp[x][1][0][1]=max(0,dp[x][0][0][0]+max2+max3);
//	cout<<x<<' '<<dp[x][0][0][0]<<' '<<dp[x][0][0][1]<<' '<<dp[x][1][1][0]<<' '<<dp[x][1][0][1]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l;
	cin>>n;
	for(i=1;i<n;i++){
		cin>>j>>k>>l;
		adj[j].push_back({k,l});
		adj[k].push_back({j,l});
	}
	dfs(1,1,0);
	cout<<max(max(dp[1][1][0][1],dp[1][1][0][0]),max(dp[0][1][0][1],dp[0][1][0][0]));
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
60
*/
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
140
*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:8:6: warning: unused variable 'sum' [-Wunused-variable]
  int sum=0,sum1=0,max1=-inf,max2=-inf,max3=-inf;
      ^~~
beads.cpp:8:12: warning: unused variable 'sum1' [-Wunused-variable]
  int sum=0,sum1=0,max1=-inf,max2=-inf,max3=-inf;
            ^~~~

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