Submission #296049

#	Time	Username	Problem	Language	Result	Execution time	Memory
296049		nafis_shifat	Power Plant (JOI20_power)	C++14	100 / 100	294 ms	41140 KiB

power

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=2e5+5;
const int inf=1e9;


vector<int> adj[mxn];
int dp[mxn][2]={};
int ans[mxn]={};
int tp[mxn]={};
int sz[mxn]={};
int fa[mxn]={};
void dfs1(int cur,int prev) {
	sz[cur]=(tp[cur]==1);
	fa[cur]=(tp[cur]==1);

	for(int u: adj[cur]) {
		if(u==prev) continue;
		dfs1(u,cur);
		sz[cur]+=sz[u];

		if(tp[cur]==0) {
			fa[cur]+=fa[u];
		}
	}
}




void dfs(int cur,int prev) {



	

	int mx1=0;

	int sm=0;
	int mx2=0;

	int sm2=0;

	int mx3=0;


	for(int u : adj[cur]) {
		if(u==prev)continue;

		dfs(u,cur);

		mx1=max(mx1,dp[u][0]);
		mx2=max(mx2,fa[u]);
		mx3=max(mx3,dp[u][1]);


		sm+=fa[u];
		sm2+=max(fa[u],dp[u][1]);

	}

	if(tp[cur]==0) {
		dp[cur][0]=max({mx1,mx2,sm});

		dp[cur][1]=sm2;
		ans[cur]=max(dp[cur][0],dp[cur][1]);
	} else {
		
		dp[cur][0]=max({mx2+1,mx3+1});
		dp[cur][1]=max({mx3-1,mx2-1,sm2-1,sm-1});
	
		ans[cur]=max({dp[cur][0],mx1,mx3+1,mx2+1,sm2-1,sm-1});
	}




}

int main() {
	int n;
	cin>>n;
	for(int i=1;i<n;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	string s;
	cin>>s;

	for(int i=0;i<n;i++) tp[i+1]=s[i]-'0';

	dfs1(1,-1);
    dfs(1,-1);
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,ans[i]);

    cout<<res<<endl;





}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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