Submission #294255

#	Time	Username	Problem	Language	Result	Execution time	Memory
294255		wilwxk	Power Plant (JOI20_power)	C++17	100 / 100	273 ms	27280 KiB

power

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

const int MAXN = 2e5+5;
vector<int> g[MAXN];
char special[MAXN];
int subsum[MAXN], dp[MAXN];
int n, ans;

void predfs(int u, int p) {
	for (auto v : g[u]) {
		if (v == p) continue;
		predfs(v, u);
		subsum[u] += dp[v];
	}
	dp[u] = subsum[u];
	if (special[u] == '1') dp[u] = max(dp[u]-1, 1); 
	// printf("idp %d %d\n", u, dp[u]);
}

void dfs(int u, int p) {
	if (special[u] == '1') {
		int cnt = 0;
		for (auto v : g[u]) cnt += dp[v] != 0;
		if (cnt <= 1) ans = max(subsum[u]+1, ans);
		else ans = max(dp[u], ans);
	}
	else {
		ans = max(ans, dp[u]);
	}
	// printf("dp %d %d %d %d\n", u, dp[u], subsum[u], ans);
	for (auto v : g[u]) {
		if (v == p) continue;

		int subu = subsum[u];
		int subv = subsum[v];
		int dpu = dp[u];
		int dpv = dp[v];
		
		subsum[u] -= dp[v];
		dp[u] = subsum[u];
		if (special[u] == '1') dp[u] = max(dp[u]-1, 1);
		subsum[v] += dp[u];
		dp[v] = subsum[v];
		if (special[v] == '1') dp[v] = max(dp[v]-1, 1);

		dfs(v, u);

		subsum[u] = subu;
		subsum[v] = subv;
		dp[u] = dpu;
		dp[v] = dpv;
	}
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n-1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	scanf(" %s", &special[1]);

	predfs(1, 1);
	dfs(1, 1);

	printf("%d\n", ans);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
power.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf(" %s", &special[1]);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~

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