Submission #709678

#	Time	Username	Problem	Language	Result	Execution time	Memory
709678		Antekb	Power Plant (JOI20_power)	C++17	100 / 100	232 ms	28848 KiB

power

#include<bits/stdc++.h>

#define st first
#define nd second
#define eb emplace_back
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){cerr<<h;if(sizeof...(t))cerr<<", ";debug(t...);};
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=2e5+5, INF=1e9+5;
vi E[N];
string s;
int dp[N];
int ans=0;
void dfs(int v, int p){
	int m=0;
	for(int u:E[v]){
		if(u!=p){
			dfs(u, v);
			dp[v]+=dp[u];
			m=max(m, dp[u]);
		}
	}
	if(s[v-1]-'0'){
		ans=max(ans, m+1);
		dp[v]=max(1, dp[v]-1);
	}
	ans=max(ans, dp[v]);
	//deb(v, dp[v]);
}
int main(){
	//ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	cin>>n;
	for(int i=1; i<n; i++){
		int u, v;
		cin>>u>>v;
		E[u].pb(v);
		E[v].pb(u);
	}
	cin>>s;
	dfs(1, 0);
	cout<<ans;
}

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