Submission #1263545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263545		NikoBaotic	Power Plant (JOI20_power)	C++20	100 / 100	115 ms	27868 KiB

power

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 2e5 + 10;

int n;
vector<int> adj[N];
int par[N];
int dp[N][2];
string s;

void dfs(int node) {
	for (int x : adj[node]) {
		if (par[node] == x) continue;
		par[x] = node;
		dfs(x);
	}
}

int run(int node, bool on) {
	if (dp[node][on] != -1) return dp[node][on];

	int ans = 0;

	if (s[node - 1] == '1') {
		ans = 1;

		if (on == 0) {
			for (int x : adj[node]) {
				if (par[node] == x) continue;

				ans = max(ans, run(x, 0));
				ans = max(ans, run(x, 1) + 1);
			}
		}

		int sum = 0;

		for (int x : adj[node]) {
			if (par[node] == x) continue;

			sum += run(x, 1);
		}

		ans = max(sum - 1, ans);
	} else {
		int sum = 0;

		for (int x : adj[node]) {
			if (par[node] == x) continue;

			sum += run(x, 1);
		}
	
		ans = max(sum, ans);
		
		for (int x : adj[node]) {
			if (par[node] == x) continue;

			ans = max(ans, run(x, on));
		}
	}

	dp[node][on] = ans;
	return dp[node][on];
}

int main() {
	FIO;

	memset(dp, -1, sizeof dp);
	
	cin >> n;

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;

		adj[a].pb(b);
		adj[b].pb(a);
	}

	cin >> s;

	dfs(1);

	cout << run(1, 0) << endl;

	return 0;
}

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