Submission #295733

#	Time	Username	Problem	Language	Result	Execution time	Memory
295733		ChrisT	Power Plant (JOI20_power)	C++17	100 / 100	208 ms	35064 KiB

power

#include <bits/stdc++.h>
using namespace std;
const int MN = 2e5+5;
vector<int> adj[MN];
char power[MN]; int dp[MN][2];
void dfs (int cur, int p = -1) {
	int mx = 0, mx2 = 0;
	for (int i : adj[cur]) if (i != p) {
		dfs(i,cur);
		dp[cur][1] += dp[i][1]; mx = max(mx,dp[i][0]); mx2 = max(mx2,dp[i][1]);
	}
	if (power[cur] == '0') dp[cur][0] = max({dp[cur][1],mx,0}), dp[cur][1] = max(dp[cur][1],0);
	else dp[cur][0] = max({dp[cur][1]-1,mx,mx2+1,1}), dp[cur][1] = max({dp[cur][1],mx2,2})-1;
}
int main () {
	int n;
	scanf ("%d",&n);
	for (int i = 1; i < n; i++) {
		int a,b;
		scanf ("%d %d",&a,&b);
		adj[a].push_back(b); adj[b].push_back(a);
	}
	scanf ("%s",power+1);
	dfs(1);
	printf ("%d\n",max(dp[1][1],dp[1][0]));
	return 0;
}

Compilation message (stderr)

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

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