제출 #1255475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255475		Seyyed_Mojtaba_Mortazavi	Power Plant (JOI20_power)	C++20	100 / 100	269 ms	36760 KiB

power

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5 + 10;

int dp[MAXN][2];
bool mark[MAXN];
vector <int> e[MAXN];

void dfs(int v, int par = -1)
{
	int mx1 = 0;
	int mx2 = 0;
	int sum = 0;
	for (auto u : e[v])
	{
		if (u != par)
		{
			dfs(u, v);
			sum += dp[u][1];
			mx1 = max(mx1, dp[u][0]);
			mx2 = max(mx2, dp[u][1]);
		}
	}
	dp[v][0] = max({mx1, mx2 + mark[v], sum - mark[v], (int) mark[v]});
	dp[v][1] = max((int) mark[v], sum - mark[v]);
}

signed main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int v, u;
		cin >> v >> u;
		e[v].push_back(u);
		e[u].push_back(v);
	}
	for (int i = 1; i <= n; i++)
	{
		char c;
		cin >> c;
		mark[i] = (c == '1');
	}
	dfs(1);
	cout << max(dp[1][0], dp[1][1]) << endl;
}

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