oj.uz

Submission #676964

# Submission time Handle Problem Language Result Execution time Memory
676964 2023-01-01T20:26:12 Z amirhoseinfar1385 Beads and wires (APIO14_beads) C++17
0 / 100
 5 ms 9684 KB 
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+5;
vector<pair<long long,long long>>adj[maxn];
long long dp11[maxn],dp10[maxn],dp01[maxn],dp00[maxn];
long long n;
long long inf=1e15;

void solve(long long u=1,long long par=0){
	vector<pair<long long,long long>>fake;
	for(auto x:adj[u]){
		if(x.first==par)
		{
			continue;
		}
		fake.push_back(x);
		solve(x.first,u);
	}
	//dp00
	for(auto x:fake){
		dp00[u]+=max(dp10[x.first]+x.second,dp00[x.first]);
	}	
	//dp10
	for(auto x:fake){
		dp10[u]=max(dp10[u],dp00[u]-max(dp10[x.first]+x.second,dp00[x.first])+dp00[x.first]+x.second);
	}
	//cout<<u<<" "<<dp10[u]<<" "<<dp00[u]<<endl;
    //dp11
    for(auto x:fake){
    	dp11[u]=max(dp11[u],dp00[u]-max(dp10[x.first]+x.second,dp00[x.first])+dp01[x.first]+x.second);
    }
    //dp01
    for(auto x:fake){
    	dp01[u]=max(dp01[u],dp00[u]-max(dp10[x.first]+x.second,dp00[x.first])+max(dp11[x.first]+x.second,dp01[x.first]));
    }
    if((long long)fake.size()==0){
    	dp10[u]=-(inf/100);
    	dp11[u]=-(inf/100);
    	dp01[u]=0;
    	dp00[u]=0;
    }
    if((long long)fake.size()<=1){
    	return ;
    }
    vector<long long>p1((long long)fake.size()),p0((long long)fake.size()),s1((long long)fake.size()),s0((long long)fake.size());
    for(long long i=0;i<(long long)fake.size();i++){
    	auto x=fake[i];
    	if(i==0){
    		p1[i]+=dp00[x.first]+x.second;
    		p0[i]+=max(dp10[x.first]+x.second,dp00[x.second]);
    	}
    	else{	
    		p1[i]=p1[i-1];
    		p0[i]=p0[i-1];
    		p1[i]=max(p0[i-1]+dp00[x.first]+x.second,p1[i-1]+max(dp10[x.first]+x.second,dp00[x.second]));
    		p0[i]+=max(dp10[x.first]+x.second,dp00[x.second]);
    	}
    }
    for(long long i=(long long)fake.size()-1;i>=0;i--){
   		auto x=fake[i];
    	if(i==(int)fake.size()-1){
    		s1[i]+=dp00[x.first]+x.second;
    		s0[i]+=max(dp10[x.first]+x.second,dp00[x.second]);
    	}
    	else{	
    		s1[i]=s1[i+1];
    		s0[i]=s0[i+1];
    		s1[i]=max(s0[i+1]+dp00[x.first]+x.second,s1[i+1]+max(dp10[x.first]+x.second,dp00[x.second]));
    		s0[i]+=max(dp10[x.first]+x.second,dp00[x.second]);
    	}
    }
    for(long long i=0;i<(long long)fake.size();i++){
    	auto x=fake[i];
    	if(i==0){
    		dp01[u]=max(dp01[u],dp01[x.first]+x.second+s1[i+1]);
   // 		cout<<x.first<<" "<<s1[i+1]<<endl;
    	}
    	else if(i==(long long)fake.size()-1){
    		dp01[u]=max(dp01[u],dp01[x.first]+x.second+p1[i-1]);
   // 		cout<<x.first<<" "<<p1[i-1]<<endl;
    	}
    	else{
    		dp01[u]=max(dp01[u],dp01[x.first]+x.second+s1[i+1]+p0[i-1]);
       		dp01[u]=max(dp01[u],dp01[x.first]+x.second+p1[i-1]+s0[i+1]);
    //   		cout<<x.first<<" "<<p1[i-1]<<" "<<p0[i-1]<<endl;
      // 		cout<<x.first<<" "<<s1[i+1]<<" "<<s0[i+1]<<endl;
    	}
    }
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=0;i<maxn;i++){
		dp10[i]=dp11[i]=dp01[i]=-inf;
	}
	for(long long i=0;i<n-1;i++){
		long long u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	solve();
	//cout<<dp00[1]<<" "<<dp01[1]<<endl;
	long long res=max(dp01[1],dp00[1]);
	cout<<res<<endl;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Incorrect 5 ms 9684 KB Output isn't correct
4 Halted 0 ms 0 KB -