Submission #927937

#	Time	Username	Problem	Language	Result	Execution time	Memory
927937		TAhmed33	Power Plant (JOI20_power)	C++98	100 / 100	168 ms	32312 KiB

power

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
const int MAXN = 2e5 + 25;
vector <int> adj[MAXN];
int n, dp[MAXN][2];
bool ok[MAXN];
void dfs (int pos, int par) {
	dp[pos][1] = ok[pos];
	int sum = 0, mx = 0, mx2 = 0;
	for (auto j : adj[pos]) {
		if (j == par) continue;
		dfs(j, pos);
		sum += dp[j][1];
		mx = max(mx, dp[j][1]);
		mx2 = max(mx2, dp[j][0]);
	}
	dp[pos][1] = max(dp[pos][1], sum - ok[pos]);
	dp[pos][0] = max({sum - ok[pos], ok[pos] + mx, mx2});
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		char c; cin >> c; ok[i] = c == '1';
	}
	dfs(1, -1);
	cout << dp[1][0] << '\n';
}

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