Submission #765319

#	Time	Username	Problem	Language	Result	Execution time	Memory
765319		siewjh	Power Plant (JOI20_power)	C++17	100 / 100	125 ms	25292 KiB

power

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 200'005;
vector<int> adjlist[MAXN];
string str;
int ans = 0;
int dfs(int x, int par) {
	int take = 0, notake = 0;
	if (str[x] == '1') {
		notake--;
		for (int nxt : adjlist[x]) {
			if (nxt == par) continue;
			int val = dfs(nxt, x);
			take = max(take, val);
			notake += val;
		}
		ans = max(ans, max(notake, take + 1));
		return max(notake, 1);
	}
	else {
		for (int nxt : adjlist[x]) {
			if (nxt == par) continue;
			int val = dfs(nxt, x);
			notake += val;
		}
		ans = max(ans, notake);
		return notake;
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes; cin >> nodes;
	for (int i = 0; i < nodes - 1; i++) {
		int a, b; cin >> a >> b;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	cin >> str;
	str = ' ' + str;
	dfs(1, -1);
	cout << ans;
	return 0;
}

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