Submission #1255436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255436		arashmemar	Power Plant (JOI20_power)	C++20	100 / 100	128 ms	27124 KiB

power

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

const int maxn = 2e5 + 100;

int dp[2][maxn];

vector <int> ne[maxn];
bool mark[maxn];
string str;

void dfs(int v)
{
	if (str[v - 1] == '1')
	{
		dp[1][v] = dp[0][v] = 1;
	}
	mark[v] = 1;
	int s = 0;
	for (auto u : ne[v])
	{
		if (mark[u])
		{
			continue;
		}
		dfs(u);
		s += dp[1][u];
		dp[0][v] = max(dp[0][v], max(dp[0][u], dp[1][u] + (str[v - 1] == '1')));
	}
	dp[1][v] = max(dp[1][v], s - (str[v - 1] == '1'));
	dp[0][v] = max(dp[0][v], s - (str[v - 1] == '1'));
	return ;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1;i < n;i++)
	{
		int v, u;
		cin >> v >> u;
		ne[v].push_back(u);
		ne[u].push_back(v);
	}
	cin >> str;
	dfs(1);

	cout << dp[0][1];
}

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