Submission #292920

#	Time	Username	Problem	Language	Result	Execution time	Memory
292920		arnold518	Power Plant (JOI20_power)	C++14	100 / 100	311 ms	28536 KiB

power

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

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

const int MAXN = 2e5;

int N;
vector<int> adj[MAXN+10];
int T[MAXN+10];

int ans=0;
int dp[MAXN+10];

void dfs(int now, int bef)
{
	dp[now]=0;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now);
		if(T[nxt]) dp[now]+=max(1, dp[nxt]-1);
		else dp[now]+=dp[nxt];
	}
}

void dfs2(int now, int bef)
{
	if(T[now])
	{
		int v=0;
		for(int nxt : adj[now])
		{
			if(T[nxt]) v=max(v, max(1, dp[nxt]-1));
			else v=max(v, dp[nxt]);
		}
		ans=max(ans, v+1);
	}
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;

		int p=dp[nxt], q=dp[now];

		if(T[nxt]) dp[now]-=max(1, dp[nxt]-1);
		else dp[now]-=dp[nxt];

		if(T[now]) dp[nxt]+=max(1, dp[now]-1);
		else dp[nxt]+=dp[now];

		dfs2(nxt, now);

		dp[nxt]=p; dp[now]=q;
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1; i<=N; i++) scanf("%1d", &T[i]);

	for(int i=1; i<=N; i++)
	{
		if(!T[i]) continue;
		dfs(i, i);
		dfs2(i, i);
		break;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

power.cpp: In function 'int main()':
power.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
power.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~
power.cpp:69:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  for(int i=1; i<=N; i++) scanf("%1d", &T[i]);
      |                          ~~~~~^~~~~~~~~~~~~~

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