Submission #1050476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050476		n1k	Power Plant (JOI20_power)	C++17	100 / 100	128 ms	35292 KiB

power

#include <bits/stdc++.h>

#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL

using namespace std;

using ll = long long;

#define all(a) (a).begin(), (a).end()

void umax(ll &a, ll b){
	a = max(a, b);
}

void solve(){
	int n; cin >> n;
	vector<vector<int>> g(n);
	for(int i=0; i+1<n; i++){
		int u, v; cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	string s; cin >> s;
	// active, notactive, best
	// active >= not active
	ll best = 0;
	vector<ll> active(n, -1e9);
	function<void(int, int)> dfs = [&](int u, int p){
		ll sum = 0, mx = 0;
		for(int v:g[u]){
			if(v==p){
				continue;
			}
			dfs(v, u);
			sum += active[v];
			umax(mx, active[v]);
		}
		// activate or not activate
		// activate
		if(s[u]=='1'){
			// not activate childs
			umax(active[u], 1);
			// not activate parents
			umax(best, mx + 1);
		}
		// not activate
		if(s[u]=='1'){
			// broken
			umax(active[u], sum - 1);
		}else{
			umax(active[u], sum);
		}
		debug(active[u]);
	};

	dfs(0, -1);

	cout<<max(best, *max_element(active.begin(), active.end()))<<endl;
}

int main(){
	solve();
	return 0;
}

Compilation message (stderr)

power.cpp: In lambda function:
power.cpp:6:21: warning: statement has no effect [-Wunused-value]
    6 | #define debug(x...) 0
      |                     ^
power.cpp:58:3: note: in expansion of macro 'debug'
   58 |   debug(active[u]);
      |   ^~~~~

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