Submission #1136115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136115		Math4Life2020	Beads and wires (APIO14_beads)	C++20	100 / 100	187 ms	41888 KiB

beads

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

using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
ll ans = -1;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	vector<pii> adj[N];
	for (ll i=0;i<(N-1);i++) {
		ll a,b,c; cin >> a >> b >> c;
		a--; b--;
		adj[a].push_back({b,c});
		adj[b].push_back({a,c});
	}
	vector<pii> fadj[N];
	pii radj[N];
	queue<ll> q0;
	q0.push(0);
	radj[0]={-1,-INF};
	vector<ll> itpls;
	while (!q0.empty()) {
		ll x = q0.front(); q0.pop();
		itpls.push_back(x);
		for (pii p0: adj[x]) {
			if (p0.first!=radj[x].first) {
				fadj[x].push_back(p0);
				radj[p0.first]={x,p0.second};
				q0.push(p0.first);
			}
		}
	}
	//dp: sum of blue
	ll dp0[N]; //no blue center up
	ll dp1[N]; //blue going up with center at this point
	for (ll x=0;x<N;x++) {
		dp0[x]=-INF;
		dp1[x]=-INF;
	}
	for (ll IND=(N-1);IND>=0;IND--) {
		ll x = itpls[IND];
		//cout << x << "\n";
		if (fadj[x].size()==0) {
			dp1[x]=-INF;
			dp0[x]=0;
			continue;
		}
		ll dp0v = 0;
		vector<ll> vaug;
		for (pii p0: fadj[x]) {
			dp0v += max(dp1[p0.first],dp0[p0.first]);
			vaug.push_back((dp0[p0.first]+p0.second)-max(dp1[p0.first],dp0[p0.first]));
		}
		sort(vaug.begin(),vaug.end());
		dp0[x]=dp0v;
		if (vaug.size()>=1) {
			dp1[x]=dp0v+vaug[vaug.size()-1]+radj[x].second;
		} else {
			dp1[x]=-INF;
		}
	}
	ans = max(ans,dp0[0]);
	//multiple root DP:
	//dp0[x] gives value of subtree of x if you assume x is the root
	//now just like dp down 
	ll dp0U[N]; //no blue segments with center x already created
	ll dp1U[N]; //dp1U[x]: blue segment at center x, one edge up (counted), one edge down to children (not counted)
	dp0U[0]=0;
	dp1U[0]=-INF;
	for (ll i=1;i<N;i++) {
		dp0U[i]=-INF;
		dp1U[i]=-INF;
	}
	for (ll IND=0;IND<N;IND++) {
		ll x = itpls[IND];
		//process all children (y) of x
		//cases: y - x - y': read dp0U[x]
		//y - x - p[x]: read dp1U[x]
		//or no edge through x
		//if y'-x edge: read dp1[y'], else read dp0[y']
		//also: 
		//x - y - ?: write dp1U[y], else write dp0U[y]
		ll sst = 0;
		multiset<ll> sup; 
		for (pii p0: fadj[x]) {
			ll y = p0.first;
			ll ve = p0.second;
			sst += max(dp0[y],dp1[y]);
			sup.insert(dp0[y]+ve-max(dp0[y],dp1[y]));
		}
		//case 1: y-x-y'
		if (fadj[x].size()>=2) {
			for (pii p0: fadj[x]) {
				ll y = p0.first;
				ll ve = p0.second;
				ll vdel = dp0[y]+ve-max(dp0[y],dp1[y]);
				sup.erase(sup.find(vdel));
				dp0U[y]=max(dp0U[y],dp0U[x]+ve+*(--sup.end())+sst-max(dp0[y],dp1[y]));
				sup.insert(vdel);
			}
		}
		//case 2: y-x-p[x]
		if (dp1U[x]!=-INF) {
			for (pii p0: fadj[x]) {
				ll y = p0.first;
				ll ve = p0.second;
				dp0U[y]=max(dp0U[y],dp1U[x]+ve+sst-max(dp0[y],dp1[y]));
			}
		}
		//case 3: child(y)-y-x
		for (pii p0: fadj[x]) {
			ll y = p0.first;
			ll ve = p0.second;
			dp1U[y]=max(dp1U[y],dp0U[x]+ve+sst-max(dp0[y],dp1[y]));
		}
		//case 4: no such edges
		for (pii p0: fadj[x]) {
			ll y = p0.first;
			dp0U[y]=max(dp0U[y],dp0U[x]+sst-max(dp0[y],dp1[y]));
		}
	}
	for (ll x=0;x<N;x++) {
		ans = max(ans,dp0[x]+dp0U[x]);
	}
	cout << ans << "\n";
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43