Submission #1115764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115764		Math4Life2020	Power Plant (JOI20_power)	C++17	0 / 100	1 ms	336 KiB

power

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

using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e9;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	ll ans = 0;
	vector<ll> adj[N];
	vector<ll> fadj[N];
	for (ll i=0;i<(N-1);i++) {
		ll a,b; cin >> a >> b;
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<bool> found(N,false);
	vector<ll> radj(N,-1);
	queue<ll> q0;
	q0.push(0);
	ll fdegL[N];
	queue<ll> q1;
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		for (ll y: adj[x]) {
			if (y != radj[x]) {
				fadj[x].push_back(y);
				radj[y]=x;
				q0.push(y);
			}
		}
		fdegL[x]=fadj[x].size();
		if (fdegL[x]==0) {
			q1.push(x);
		}
	}
	bool S[N];
	string s1; cin >> s1;
	for (ll i=0;i<N;i++) {
		if (s1[i]=='1') {
			S[i]=1;
		} else {
			assert(s1[i]=='0');
			S[i]=0;
		}
	}
	ll dp0[N]; //dp on: you know that it has to connect down; given that it 
	//does this, what is the max value?
	ll dp1[N]; //does not connect down; what's the max value?
	while (!q1.empty()) {
		ll x = q1.front(); q1.pop();
		if (fadj[x].size()==0) {
			dp0[x]=-INF;
			dp1[x]=S[x];
		} else {
			dp1[x]=S[x];
			ll mx=-INF; ll sm=0; //max and sum
			for (ll y: fadj[x]) {
				ll vy = max(dp1[y],dp0[y]);
				mx = max(mx,vy);
				sm += vy;
			}
			//cout << "mx,sm,dp1="<<mx<<","<<sm<<","<<dp1[x]<<"\n";
			ans = max(ans,dp1[x]+mx);
			dp0[x]=sm-dp1[x];
			ans = max(ans,dp0[x]);
		}
		if (radj[x]!=-1) {
			fdegL[radj[x]]--;
			if (fdegL[radj[x]]==0) {
				q1.push(radj[x]);
			}
		}
	}
	cout << ans << "\n";
}

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