Submission #495675

#	Time	Username	Problem	Language	Result	Execution time	Memory
495675		minhcool	Power Plant (JOI20_power)	C++17	100 / 100	176 ms	27460 KiB

power

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 2e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n;
bool plant[N];

vector<int> Adj[N];

/*
Basically, there are three main cases:
- Not choosing subtree of u (including u)
- Just choosing subtree of u
- Not just choosing subtree of u -> every node that is parent of at least one node in subtree u is broken
*/

int dp[N][2];// cases above (ofc first case -> 0)

int par[N];

void dfs(int u, int p){
	par[u] = p;
	for(auto v : Adj[u]){
		if(v == p) continue;
		dfs(v, u);
	}
	int mx = 0;
	for(auto v : Adj[u]){
		if(v == p) continue;
		dp[u][0] += max(dp[v][1], 0LL);// you can not choose anything in v
		mx = max(mx, dp[v][1]);
	}
	dp[u][0] -= plant[u];
	dp[u][0] = max(dp[u][0], mx + plant[u]);// just choosing one subtree of u => you can choose u 
	dp[u][1] = plant[u];// just choosing u
	int sum = 0;
	for(auto v : Adj[u]){
		if(v == p) continue;
		sum += max(0LL, dp[v][1]);
	}
	sum -= plant[u];
	dp[u][1] = max(dp[u][1], sum);
}

void process(){
	cin >> n;
	for(int i = 1; i < n; i++){
		int x, y;
		cin >> x >> y;
		Adj[x].pb(y);
		Adj[y].pb(x);
	}
	string s;
	cin >> s;
	for(int i = 1; i <= n; i++) plant[i] = s[i - 1] - '0';
	dfs(1, 1);
	int mx = -1;
	for(int i = 1; i <= n; i++) mx = max(mx, dp[i][0]);
	cout << mx;
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

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