Submission #970998

#	Time	Username	Problem	Language	Result	Execution time	Memory
970998		starchan	Power Plant (JOI20_power)	C++17	100 / 100	120 ms	36936 KiB

power

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int MX = 2e5+5;
const int INF = 1e17;

vector<int> adj[MX];
bool S[MX];
int dp[2][2][MX];

void dfs(int u, int p)
{
	int V = 0; int W = 0; int UU = 0;
	int rr = 0;
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		rr++;
		dfs(v, u);
		V = max(V, max(dp[0][0][v], dp[0][1][v]));
		UU = max(UU, max(dp[1][0][v], dp[1][1][v]));
		W+=max(dp[1][0][v], dp[1][1][v]);
	}
	if(rr == 0)
	{
		dp[0][0][u] = 0;
		dp[0][1][u] = S[u];
		dp[1][0][u] = 0;
		dp[1][1][u] = S[u];
		return;
	}
	//Case: Nothing selected at u, or its parent.
	//We ignore the root, and compute cost without it. Yet, we enable the foundation.
	dp[0][0][u] = max(0ll, max(V, W-S[u]));
	dp[0][1][u] = max(0ll, max(UU+S[u], W-S[u]));
	dp[1][0][u] = max(0ll, max(UU-S[u], W-S[u]));
	dp[1][1][u] = max(0ll, max(S[u]+0ll, max(UU-S[u], W-S[u])));
	return;
}

signed main()
{
	fast();
	int n;
	cin >> n;
	for(int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		adj[u].pb(v); adj[v].pb(u);
	}
	for(int i = 1; i <= n; i++)
	{
		char c; cin >> c;
		S[i] = (c=='1');
	}
	dfs(1, 0);
	cout << (max(dp[0][1][1], dp[0][0][1])) << "\n";
	return 0;
}	

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