Submission #1115780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115780		Math4Life2020	Power Plant (JOI20_power)	C++17	100 / 100	142 ms	34800 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;
	if (N==1) {
		cout << "1\n"; exit(0);
	}
	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;
	vector<ll> radj;
	for (ll i=0;i<N;i++) {
		radj.push_back(-1);
		found.push_back(0);
	}
	queue<ll> q0;
	q0.push(0);
	ll fdegL[N];
	queue<ll> q1;
	vector<ll> tpls;
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		tpls.push_back(x);
		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?
	ll NUMFOUND=0;
	/*while (!q1.empty()) {
		ll x = q1.front(); q1.pop();
		NUMFOUND++;
		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 += max(0LL,vy);
			}
			assert(mx!=(-INF));
			//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]);
			}
		}
	}*/
	for (ll i=(N-1);i>=0;i--) {
		ll x = tpls[i];
		NUMFOUND++;
		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 += max(0LL,vy);
			}
			assert(mx!=(-INF));
			//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]);
			}
		}
	}
	assert(NUMFOUND==N);
	cout << ans;
}

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