Submission #962482

#	Time	Username	Problem	Language	Result	Execution time	Memory
962482		0npata	Power Plant (JOI20_power)	C++17	100 / 100	200 ms	29668 KiB

power

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

const int N = 200'000;

#define vec vector
#define pb push_back

int dp[N][2];
vec<int> tree[N];
string s;

void dfs(int u, int p = -1) {
	for(int v : tree[u]) {
		if(p==v) continue;

		dfs(v, u);
	}

	int a = 1; int b = -1; int c = 0;
	for(int v : tree[u]) {
		if(v==p) continue;
		a = max(dp[v][1]+1, a);
		b += dp[v][1];
		c = max(dp[v][0], c);
	}
	if(s[u] == '1') {
		dp[u][0] = max(max(a, b), c);
		dp[u][1] = max(b, 1);
	}
	else {
		dp[u][1] = b+1;
		dp[u][0] = max(c, b+1);
	}
}

int main() {
	int n;
	cin >> n;
	for(int i = 0; i<n-1; i++) {
		int u, v;
		cin >> u >> v;
		u--; v--;

		tree[u].pb(v);
		tree[v].pb(u);
	}

	cin >> s;

	dfs(0);

	cout << dp[0][0] << '\n';

}

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