Submission #768822

#	Time	Username	Problem	Language	Result	Execution time	Memory
768822		jmyszka2007	Power Plant (JOI20_power)	C++17	100 / 100	123 ms	33192 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pb push_back
constexpr int LIM = 2e5;
int dp[LIM + 10][2];
bool czy[LIM + 10];
int cnt[LIM + 10];
vi g[LIM + 10];
void cntdp(int v, int o) {
	if(czy[v]) {
		cnt[v] = 1;
	}
	int sum0 = 0, sum1 = 0;
	int mx0 = 0, mx1 = 0;
	for(auto x : g[v]) {
		if(x != o) {
			cntdp(x, v);
			cnt[v] += cnt[x];
			mx0 = max(mx0, dp[x][0]);
			mx1 = max(mx1, dp[x][1]);
			sum0 += dp[x][0];
			sum1 += dp[x][1];
		}
	}
	//dp[v][0] - nie wchodzi od gory
	//dp[v][1] - wchodzi od gory
	int ile = 0;
	for(auto x : g[v]) {
		if(x != o) {
			if(cnt[v]) {
				ile++;
			}
		}
	}
	if(czy[v]) {
		dp[v][0] = max({mx1 + 1, mx0, sum1 - 1});
		dp[v][1] = max(sum1 - 1, 1);
	}
	else {
		dp[v][0] = max({mx0, sum1});
		dp[v][1] = sum1;
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	string tmp;
	cin >> tmp;
	for(int i = 1; i <= n; i++) {
		if(tmp[i - 1] == '1') {
			czy[i] = 1;
		}
	}
	cntdp(1, 1);
	cout << dp[1][0] << '\n';
}

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