Submission #650253

#	Time	Username	Problem	Language	Result	Execution time	Memory
650253		ymm	Beads and wires (APIO14_beads)	C++17	100 / 100	224 ms	28692 KiB

beads

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 200'010;
vector<pii> A[N];
int n;

array<int, 4> dfs(int v, int p, int w)
{
	int sum0 = 0;
	vector<pii> v20, v10w, v30w;
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		auto x = dfs(u, v, e);
		v20.emplace_back(x[2] - x[0], u);
		v10w.emplace_back(x[1] - x[0] + e, u);
		v30w.emplace_back(x[3] - x[0] + e, u);
		sum0 += x[0];
	}
	v20.push_back({-1e9, -1}); v20.push_back({-1e9, -2});
	v10w.push_back({-1e9, -3}); v10w.push_back({-1e9, -4});
	v30w.push_back({-1e9, -5}); v30w.push_back({-1e9, -6});
	sort(v20.rbegin(), v20.rend());
	sort(v10w.rbegin(), v10w.rend());
	sort(v30w.rbegin(), v30w.rend());
	array<int, 4> ans = {};
	ans[0] = sum0 + v10w[0].first + w;
	ans[1] = 0;
	if (v30w[0].second != v10w[0].second) {
		ans[3] = sum0 + v30w[0].first + v10w[0].first;
	} else {
		ans[3] = sum0 + max(v30w[0].first + v10w[1].first,
		                    v30w[1].first + v10w[0].first);
	}
	ans[2] = max(ans[3], sum0 + v30w[0].first + w);
	ans[0] = max(ans[0], sum0);
	ans[1] = max(ans[1], sum0);
	ans[2] = max(ans[2], sum0 + v20[0].first);
	ans[3] = max(ans[3], sum0 + v20[0].first);
	Loop (i,0,4)
		ans[i] = max(ans[i], 0);
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop (i,1,n) {
		int v, u, w;
		cin >> v >> u >> w;
		--v; --u;
		A[v].push_back({u, w});
		A[u].push_back({v, w});
	}
	cout << dfs(0, -1, 0)[3] << '\n';
}

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