Submission #951807

#	Time	Username	Problem	Language	Result	Execution time	Memory
951807		dio_2	Power Plant (JOI20_power)	C++17	100 / 100	91 ms	28708 KiB

power

#include<bits/stdc++.h>
using namespace std;

const int nax = (int)2e5 + 10;
bool isGen[nax];
vector<int> g[nax];
int ans;
int dp[nax];

void dfs(int u, int par){
	if(isGen[u]){
		int best = 0;
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
			best = max(best, dp[v] + 1); // use the Generator on v.
		}
		ans = max(ans, best);
		dp[u]--; // because i have generator and it will break
		dp[u] = max(dp[u], 1); // it will break only if i have > 2.
	} else {
		for(int v : g[u]) if(v != par){
			dfs(v, u);
			dp[u] += dp[v];
		}
	}
	ans = max(ans, dp[u]);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	for(int i = 1;i < n;i++){
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	
	for(int i = 1;i <= n;i++){
		char c; cin >> c;
		if(c == '1') isGen[i] = 1;
	}
	
	dfs(1, -1);
	
	cout << ans << '\n';
	
	return 0;
}

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