Submission #306041

#	Time	Username	Problem	Language	Result	Execution time	Memory
306041		TadijaSebez	Power Plant (JOI20_power)	C++11	100 / 100	1116 ms	27896 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
vector<int> E[N];
char s[N];
int sz[N],was[N];
void DFS(int u,int p){sz[u]=1;for(int v:E[u])if(!was[v]&&v!=p)DFS(v,u),sz[u]+=sz[v];}
int Find(int u,int p,int n){for(int v:E[u])if(!was[v]&&v!=p&&sz[v]*2>=n)return Find(v,u,n);return u;}
int Find(int u){DFS(u,u);u=Find(u,u,sz[u]);was[u]=1;return u;}
int ans,dp[N];
void DP(int u,int p){
	int sum=0;
	dp[u]=s[u]=='1'?1:0;
	for(int v:E[u])if(!was[v]&&v!=p){
		DP(v,u);
		sum+=dp[v];
	}
	if(s[u]=='1')dp[u]=max(dp[u],sum-1);
	else dp[u]=max(dp[u],sum);
}
void Decompose(int u){
	u=Find(u);
	int sum=0;
	for(int v:E[u])if(!was[v]){
		DP(v,u);
		if(s[u]=='1')ans=max(ans,dp[v]+1);
		sum+=dp[v];
	}
	if(s[u]=='1')ans=max(ans,sum-1),ans=max(ans,1);
	else ans=max(ans,sum);
	for(int v:E[u])if(!was[v])Decompose(v);
}
int main(){
	int n;
	scanf("%i",&n);
	for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	scanf("%s",s+1);
	Decompose(1);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
power.cpp:37:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |  for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
      |                          ~~~~~^~~~~~~~~~~~~~~
power.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~

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