Submission #292865

#	Time	Username	Problem	Language	Result	Execution time	Memory
292865		luciocf	Power Plant (JOI20_power)	C++14	100 / 100	285 ms	28664 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5+10;

int tem[maxn];

int dp[maxn];
int soma[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	if (tem[u] && p) dp[u] = 2;

	int mx = 0;

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		dfs(v, u);

		mx = max(mx, dp[v]-tem[v]);

		soma[u] += dp[v]-tem[v];
	}

	if (p == 0) dp[u] = max(dp[u], mx);
	else dp[u] = max(dp[u], soma[u]);
}

int ans;

void solve(int u, int p)
{
	if (tem[u]) ans = max(ans, dp[u]+1);

	for (auto v: grafo[u])
	{
		if (v == p) continue;

		int dp_ant = dp[u], soma_ant = soma[u];

		soma[u] -= (dp[v]-tem[v]);

		if (tem[u]) dp[u] = max(2, soma[u]);
		else dp[u] = max(0, soma[u]);

		soma[v] += dp[u]-tem[u];

		if (tem[v])
		{
			dp[v] = 0;
			for (auto w: grafo[v])
				dp[v] = max(dp[v], dp[w]-tem[w]);
		}
		else dp[v] = max(0, soma[v]);

		solve(v, u);

		dp[u] = dp_ant, soma[u] = soma_ant;
	}
}

int main(void)
{
	int n;
	scanf("%d", &n);

	for (int i = 1; i < n; i++)
	{
		int u, v;
		scanf("%d %d", &u, &v);

		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}

	for (int i = 1; i <= n; i++)
	{
		char c;
		scanf(" %c", &c);

		if (c == '1') tem[i] = 1;
	}

	int r = 0;
	for (int i = 1; i <= n; i++)
		if (tem[i])
			r = i;

	dfs(r, 0);
	solve(r, 0);

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

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
power.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   76 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~
power.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |   scanf(" %c", &c);
      |   ~~~~~^~~~~~~~~~~

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