Submission #624383

#	Time	Username	Problem	Language	Result	Execution time	Memory
624383		pooyashams	Power Plant (JOI20_power)	C++14	100 / 100	153 ms	35172 KiB

power

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define endl '\n'
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 2e5+10;

vector<int> G[maxn];
int dp[maxn][2];
string s;

void dfs(int v, int p)
{
	int a = 0;
	int b = 0;
	int c = 0;
	int k = 0;
	for(int u: G[v])
	{
		if(u == p) continue;
		dfs(u, v);
		a += dp[u][1];
		b = max(b, dp[u][0]);
		c = max(c, dp[u][1]);
		k++;
	}
	if(k == 0)
	{
		dp[v][0] = dp[v][1] = (s[v]-'0');
	}
	else if(k == 1)
	{
		if(s[v] == '1')
		{
			dp[v][0] = max(c+1, b);
			dp[v][1] = max(1, a-1);
		}
		else
		{
			dp[v][0] = b;
			dp[v][1] = c;
		}
	}
	else
	{
		if(s[v] == '1')
		{
			dp[v][0] = max( max(1, a-1), max(c+1, b) );
			dp[v][1] = max(1, a-1);
		}
		else
		{
			dp[v][0] = max(a, b);
			dp[v][1] = a;
		}
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	for(int i = 1; i < n; i++)
	{
		int x, y; cin >> x >> y;
		x--; y--;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	cin >> s;
	dfs(0, 0);
	cout << dp[0][0] << endl;
	return 0;
}

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