Submission #958107

#	Time	Username	Problem	Language	Result	Execution time	Memory
958107		MinaRagy06	Beads and wires (APIO14_beads)	C++17	100 / 100	149 ms	45756 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const int N = 200'005;
const ll inf = 1e18;
ll dp[N][2];
vector<array<ll, 2>> tadj[N], adj[N];
void build(int i, int p) {
	adj[i].clear();
	for (auto [nxt, w] : tadj[i]) {
		if (nxt == p) continue;
		build(nxt, i);
		adj[i].push_back({nxt, w});
	}
}
void root(int i) {
	for (auto [nxt, w] : adj[i]) {
		root(nxt);
	}
	for (int carry = 0; carry < 2; carry++) {
		ll ans = 0;
		if (carry) {
			ans = -inf;
		}
		ll s = 0;
		for (auto [nxt, w] : adj[i]) {
			s += max(dp[nxt][1] + w, dp[nxt][0]);
		}
		if (!carry) {
			ans = s;
		} else {
			ll mx = -inf;
			for (auto [nxt, w] : adj[i]) {
				mx = max(mx, - max(dp[nxt][1] + w, dp[nxt][0]) + dp[nxt][0] + w);
			}
			ans = s + mx;
		}
		dp[i][carry] = ans;
	}
}
ll ans = 0;
void reroot(int i, array<ll, 3> up) {
	array<ll, 2> newdp = {-inf, -inf};
	for (int carry = 0; carry < 2; carry++) {
		newdp[carry] = 0;
		if (carry) {
			newdp[carry] = -inf;
		}
		ll s = 0;
		for (auto [nxt, w] : adj[i]) {
			s += max(dp[nxt][1] + w, dp[nxt][0]);
		}
		s += max(up[1] + up[2], up[0]);
		if (!carry) {
			newdp[carry] = max(newdp[carry], s);
		} else {
			ll mx = -inf;
			for (auto [nxt, w] : adj[i]) {
				mx = max(mx, - max(dp[nxt][1] + w, dp[nxt][0]) + dp[nxt][0] + w);
			}
			mx = max(mx, - max(up[1] + up[2], up[0]) + up[0] + up[2]);
			newdp[carry] = max(newdp[carry], s + mx);
		}
	}
// 	cout << i << ": " << newdp[0] << '\n';
	ans = max(ans, newdp[0]);
	int m = adj[i].size();
	ll prfmx[m + 1], sufmx[m + 1], prfs[m + 1]{}, sufs[m + 1]{};
	prfmx[0] = - max(up[1] + up[2], up[0]) + up[0] + up[2];
	sufmx[m] = -inf;
	if (max(up[1] + up[2], up[0]) > 0) {
		prfs[0] = max(up[1] + up[2], up[0]);
	}
	for (int j = 0; j < m; j++) {
		auto [nxt, w] = adj[i][j];
		prfmx[j + 1] = max(prfmx[j], - max(dp[nxt][1] + w, dp[nxt][0]) + dp[nxt][0] + w);
		prfs[j + 1] = prfs[j] + max(dp[nxt][1] + w, dp[nxt][0]);
	}
	for (int j = m - 1; j >= 0; j--) {
		auto [nxt, w] = adj[i][j];
		sufmx[j] = max(sufmx[j + 1], - max(dp[nxt][1] + w, dp[nxt][0]) + dp[nxt][0] + w);
		sufs[j] = sufs[j + 1] + max(dp[nxt][1] + w, dp[nxt][0]);
	}
	for (int j = 0; j < m; j++) {
		auto [nxt, w] = adj[i][j];
		ll s = prfs[j] + sufs[j + 1];
		ll mx = max(prfmx[j], sufmx[j + 1]);
// 		cout << j << ' ' << prfmx[j] << ' ' << sufmx[j + 1] << '\n';
		reroot(nxt, {s, s + mx, w});
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	memset(dp, -1, sizeof dp);
	int n;
	cin >> n;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		tadj[u].push_back({v, w});
		tadj[v].push_back({u, w});
	}
	memset(dp, -1, sizeof dp);
	build(1, 0);
	
	root(1);
	reroot(1, (array<ll, 3>) {-inf, -inf, -inf});	
	cout << ans << '\n';
	return 0;
}

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