Submission #1063456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063456		ThylOne	Power Plant (JOI20_power)	C++14	100 / 100	109 ms	32824 KiB

power

//####################
//PowerPlant
//####################
#include<bits/stdc++.h>

using namespace std;
const int maxiN = 2*1e5;
bool isPowerPlant[maxiN];
vector<int> links[maxiN];
int dp[2][maxiN];
int ans = 0;
int solve(bool ataken,int node,int dad=-1){
	if(dp[ataken][node]!=-1)return dp[ataken][node];
	if(ataken==0){
		int sum = 0;
		int bestsub = 0;
		for(int v:links[node])if(v!=dad){
			int x = solve(0,v,node);
			bestsub = max(bestsub,x);
			sum += x;
			ans = max(ans, isPowerPlant[node] + solve(1,v,node));
		}
		if(bestsub<1)bestsub=isPowerPlant[node];
		if(bestsub>1)bestsub-=isPowerPlant[node];
		ans = max(ans,max(sum-isPowerPlant[node],bestsub));
		return dp[ataken][node] = max(sum-isPowerPlant[node],bestsub);
	}else{
		int sum = 0;
		int bestsub = 0;
		for(int v:links[node])if(v!=dad){
			int x = solve(0,v,node);
			bestsub = max(bestsub,x);
			sum += x;
		}
		ans = max(ans, max(sum-isPowerPlant[node],bestsub));
		return dp[ataken][node] = max(sum-isPowerPlant[node],bestsub);
	}
	
}
signed main(){
	ios::sync_with_stdio(false);
	int n;cin>>n;
	for(int i = 1;i<n;i++){
		int a,b;cin>>a>>b;
		a--;
		b--;
		links[a].push_back(b);
		links[b].push_back(a);
	}
	fill(dp[0],dp[0]+n,-1);
	fill(dp[1],dp[1]+n,-1);
	string binary;cin>>binary;
	for(int i= 0;i<n;i++)isPowerPlant[i] = (binary[i]=='1');
	solve(0,0);
	cout<<ans<<endl;
	return 0;
};

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53