Submission #292586

#	Time	Username	Problem	Language	Result	Execution time	Memory
292586		kshitij_sodani	Power Plant (JOI20_power)	C++14	100 / 100	236 ms	27424 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 

int n;
vector<int> adj[200001];
int it[200001];
int dp[200001][2];
int ans=0;
void dfs(int no,int par=-1){


	for(auto j:adj[no]){
		if(j!=par){
			dfs(j,no);
		}
	}
	dp[no][1]=0;
	int su=0;
	if(it[no]){
		dp[no][1]=1;
		dp[no][0]=1;
		su-=1;
	}

	for(auto j:adj[no]){
		if(j!=par){
			su+=dp[j][1];
		}
	}
	dp[no][1]=max(dp[no][1],su);
	int ma=0;
	int ma2=0;
	for(auto j:adj[no]){
		if(j!=par){
			ma=max(ma,dp[j][1]);
			ma2=max(ma2,dp[j][0]);
		}
	}
	if(it[no]){
		ma+=1;
	}
	dp[no][0]=max(dp[no][0],ma);
	dp[no][0]=max(dp[no][0],ma2);

	int su2=0;
	if(it[no]){
		su2-=1;
	}
	for(auto j:adj[no]){
		if(j!=par){
			su2+=dp[j][1];
		}
	}
	dp[no][0]=max(dp[no][0],su2);
	ans=max(ans,max(dp[no][0],dp[no][1]));

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n-1;i++){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
	}

	for(int i=0;i<n;i++){
		char s;
		cin>>s;
		if(s=='0'){
			it[i]=0;
		}
		else{
			it[i]=1;
		}
	}
	dfs(0);
	cout<<ans<<endl;




	return 0;
}

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