Submission #391203

#	Time	Username	Problem	Language	Result	Execution time	Memory
391203		keta_tsimakuridze	Power Plant (JOI20_power)	C++14	100 / 100	291 ms	29660 KiB

power

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7;
int t,ans,dp[N],u,v,n;
string s;
vector<int>V[N];
void dfs(int u,int p){
	if(s[u]=='1')  dp[u] = 1;
	int sum = 0, mx = 0;
	for(int i=0;i<V[u].size();i++){
		if(V[u][i] == p) continue;
		dfs(V[u][i],u); 
		sum+=dp[V[u][i]];
		mx=max(mx,dp[V[u][i]]);
	}
	ans = max(ans,max(mx+(s[u]=='1'), sum - (s[u]=='1')));
	dp[u] = max(dp[u], max(mx-(s[u]=='1'),sum-(s[u]=='1')));
}
 main(){
	// t=1;
	cin>>n;
	for(int i=2;i<=n;i++){
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	cin>>s;
	s='#'+s;
	dfs(1,0);
	cout<<ans;
}

Compilation message (stderr)

power.cpp: In function 'void dfs(long long int, long long int)':
power.cpp:13:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<V[u].size();i++){
      |              ~^~~~~~~~~~~~
power.cpp: At global scope:
power.cpp:22:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 |  main(){
      |       ^

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