Submission #763104

#	Time	Username	Problem	Language	Result	Execution time	Memory
763104		nhphan0505	Power Plant (JOI20_power)	C++17	0 / 100	1 ms	212 KiB

power

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define gcd __gcd
#define endl '\n'
const int N=200050,M=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll n, u, v, cnt[N], ans;
bool plant[N], visited[N];
char c;
vector<vector<ll>> adj;

ll dfs(ll u){
	visited[u]=1;
	ll res=0, sum=0;
	for(auto v:adj[u]){
		if(!visited[v]){ 
			dfs(v);
			cnt[u]+=cnt[v];
			res=max(res, cnt[v]);
		}
	}
	ans=max(ans, res+plant[u]);
	// cout<<u<<" "<<ans<<" "<<cnt[u]<<" ";
	cnt[u]=max(cnt[u]-plant[u], 1LL*plant[u]);
	// cout<<u<<" "<<cnt[u]<<endl;
	return res;
}

signed main(){
	ios_base::sync_with_stdio(NULL); 
	cin.tie(nullptr); cout.tie(nullptr);
	cin>>n;
	adj.assign(n+1, {});
	for(ll i=1; i<n; ++i){
		cin>>u>>v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	for(ll i=1; i<=n; ++i){
		cin>>c;
		plant[i]=c-'0';
		// if(plant[i]) cout<<i<<" ";
	}
	// cout<<endl;
	dfs(1);
	cout<<max(ans, cnt[1]+plant[1]);
    return 0;
}

Compilation message (stderr)

power.cpp: In function 'll dfs(ll)':
power.cpp:20:12: warning: unused variable 'sum' [-Wunused-variable]
   20 |  ll res=0, sum=0;
      |            ^~~

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