Submission #162352

#	Time	Username	Problem	Language	Result	Execution time	Memory
162352		HungAnhGoldIBO2020	Beads and wires (APIO14_beads)	C++14	100 / 100	221 ms	24560 KiB

beads

#include<bits/stdc++.h>
#define use 1
#define mid 2
#define nouse 0
#define nomid 0
using namespace std;
const int N=2e5+1;
const int inf=1e9+7;
int dp[4][N],val[N];
vector<pair<int,int> > adj[N];
void dfs(int x,int p){
	int mx_nouse_nomid1=-inf,mx_nouse_nomid2=-inf,mx_nouse_mid1=-inf,mx_nouse_mid2=-inf,mx_mid=-inf;
	int idx_nouse_nomid1=0,idx_nouse_nomid2=0,idx_nouse_mid1=0,idx_nouse_mid2=0;
	for(auto j:adj[x]){
		int i=j.first;
		if(i!=p){
			val[i]=j.second;
			dfs(i,x);
			int pts=max(dp[nouse|nomid][i],dp[use|nomid][i]);
			dp[nouse|nomid][x]+=pts;
			mx_mid=max(mx_mid,max(dp[nouse|mid][i],dp[use|mid][i])-pts);
			int pts_nouse_nomid=dp[nouse|nomid][i]+j.second-pts;
			if(pts_nouse_nomid>mx_nouse_nomid1){
				mx_nouse_nomid2=mx_nouse_nomid1;
				idx_nouse_nomid2=idx_nouse_nomid1;
				mx_nouse_nomid1=pts_nouse_nomid;
				idx_nouse_nomid1=i;
			}
			else{
				if(pts_nouse_nomid>mx_nouse_nomid2){
					mx_nouse_nomid2=pts_nouse_nomid;
					idx_nouse_nomid2=i;
				}
			}
			int pts_nouse_mid=dp[nouse|mid][i]+j.second-pts;
			if(pts_nouse_mid>mx_nouse_mid1){
				mx_nouse_mid2=mx_nouse_mid1;
				idx_nouse_mid2=idx_nouse_mid1;
				mx_nouse_mid1=pts_nouse_mid;
				idx_nouse_mid1=i;
			}
			else{
				if(pts_nouse_mid>mx_nouse_mid2){
					mx_nouse_mid2=pts_nouse_mid;
					idx_nouse_mid2=i;
				}
			}
		}
	}
	dp[use|nomid][x]=dp[nouse|nomid][x]+mx_nouse_nomid1+val[x];
	dp[use|mid][x]=dp[nouse|nomid][x]+mx_nouse_mid1+val[x];
	dp[nouse|mid][x]=dp[nouse|nomid][x]+max(mx_mid,0);
	dp[nouse|mid][x]=max(dp[nouse|mid][x],dp[nouse|nomid][x]+mx_nouse_nomid1+mx_nouse_nomid2);
	if(idx_nouse_mid1!=idx_nouse_nomid1){
		dp[nouse|mid][x]=max(dp[nouse|mid][x],dp[nouse|nomid][x]+mx_nouse_mid1+mx_nouse_nomid1);
	}
	else{
		dp[nouse|mid][x]=max(dp[nouse|mid][x],dp[nouse|nomid][x]+mx_nouse_mid1+mx_nouse_nomid2);
		dp[nouse|mid][x]=max(dp[nouse|mid][x],dp[nouse|nomid][x]+mx_nouse_mid2+mx_nouse_nomid1);
	}
}
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);
	cout<<max(dp[nouse|mid][1],dp[nouse|nomid][1]);
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
*/
/*
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
*/

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:13:25: warning: variable 'idx_nouse_nomid2' set but not used [-Wunused-but-set-variable]
  int idx_nouse_nomid1=0,idx_nouse_nomid2=0,idx_nouse_mid1=0,idx_nouse_mid2=0;
                         ^~~~~~~~~~~~~~~~
beads.cpp:13:61: warning: variable 'idx_nouse_mid2' set but not used [-Wunused-but-set-variable]
  int idx_nouse_nomid1=0,idx_nouse_nomid2=0,idx_nouse_mid1=0,idx_nouse_mid2=0;
                                                             ^~~~~~~~~~~~~~

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