Submission #532879

#	Time	Username	Problem	Language	Result	Execution time	Memory
532879		vuhoanggiap	Power Plant (JOI20_power)	C++17	100 / 100	153 ms	28688 KiB

power

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

const int maxN = 2e5 + 5; 
int n, ans; 
bool has[maxN];
int dp[maxN];
vector<int> adj[maxN];

void dfs(int u, int p = 1) { 
	for (auto v : adj[u]) {
		if (v != p) {
			dfs(v, u); 
			dp[u] += dp[v]; 
			ans = max(ans, dp[v] + has[u]); 
		}
	}
	if (has[u]) 
		dp[u] = max(dp[u] - 1, 1); 
	dp[u] = max(dp[u], 0); 
	ans = max(ans, dp[u]); 
}

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	cin >> n; 
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; 
		adj[u].pb(v); adj[v].pb(u); 
	}
	for (int i = 1; i <= n; i++) {
		char c; cin >> c; 
		has[i] = (c == '1'); 
	}
	dfs(1); 
	cout << ans; 
}

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