Submission #684943

#	Time	Username	Problem	Language	Result	Execution time	Memory
684943		NK_	Power Plant (JOI20_power)	C++17	100 / 100	176 ms	32544 KiB

power

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N; cin >> N;
	
	vector<vector<int>> adj(N);

	for(int i = 0; i < N-1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	string S; cin >> S;

	vector<int> on(N); for(int i = 0; i < N; i++) on[i] = S[i] - '0';
	vector<int> dp(N, 0);

	function<void(int, int)> gen = [&](int u, int p) {
		dp[u] = -(S[u] - '0');
		for(auto v : adj[u]) if (v != p) {
			gen(v, u);
			dp[u] += max(dp[v], on[v]);
		}
		// cout << u << " " << max(dp[u], on[u]) << nl;
	};

	gen(0, -1);

	int ans = 0;

	function<void(int, int)> dfs = [&](int u, int p) {
		// cout << u << " " << dp[u] << nl;
		ans = max(ans, max(dp[u], on[u]));

		for(auto v : adj[u]) if (v != p) {
			ans = max(ans, max(dp[v], on[v]) + on[u]);

			dp[u] -= max(dp[v], on[v]);
			dp[v] += max(dp[u], on[u]);

			dfs(v, u);

			dp[v] -= max(dp[u], on[u]);
			dp[u] += max(dp[v], on[v]);
		}
	};

	dfs(0, -1);

	cout << ans << nl;

    return 0;
}

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