oj.uz

Submission #162228

# Submission time Handle Problem Language Result Execution time Memory
162228 2019-11-07T08:30:47 Z HungAnhGoldIBO2020 Beads and wires (APIO14_beads) C++14
0 / 100
 11 ms 5112 KB 
#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 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
		}
	}
//	cout<<max1<<' '<<max2<<' '<<max3<<'\n';
	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,-inf);
	cout<<max(max(dp[1][1][0][1],dp[1][1][0][0]),max(dp[1][0][0][0],dp[1][0][0][1]));
}
/*
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
*/
/*
4
1 2 1
1 3 2
3 4 1
3
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 11 ms 4984 KB Output is correct
3 Correct 6 ms 5112 KB Output is correct
4 Correct 7 ms 4956 KB Output is correct
5 Correct 6 ms 5112 KB Output is correct
6 Incorrect 6 ms 4984 KB Output isn't correct
7 Halted 0 ms 0 KB -