Submission #1136104

#TimeUsernameProblemLanguageResultExecution timeMemory
1136104Math4Life2020Beads and wires (APIO14_beads)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h>
using namespace std;

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

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 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;
		}
	}
	cout << dp0[0] <<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...