Submission #1136106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136106		Math4Life2020	Beads and wires (APIO14_beads)	C++20	0 / 100	2 ms	4936 KiB

beads

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

using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e18;
const ll Nm = 2e5+5;
vector<pii> adj[Nm];
ll N;

ll solve(ll ROOT) {
	vector<pii> fadj[N];
	pii radj[N];
	queue<ll> q0;
	q0.push(ROOT);
	radj[ROOT]={-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 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()>=2) {
			dp0[x]=max(dp0v,dp0v+vaug[vaug.size()-1]+vaug[vaug.size()-2]);
		}
		if (vaug.size()>=1) {
			dp1[x]=dp0v+vaug[vaug.size()-1]+radj[x].second;
		} else {
			dp1[x]=-INF;
		}
	}
	return dp0[ROOT];
}


int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> 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});
	}
	ll ans = -1;
	for (ll i=0;i<N;i++) {
		ans = max(ans,solve(i));
	}
	cout << ans << "\n";
}

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