Submission #650246

#	Time	Username	Problem	Language	Result	Execution time	Memory
650246		ymm	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	5020 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;

tuple<int,int,int> dfs(int v, int p, int w)
{
	int sum = 0;
	vector<int> vec0; // 1 - 0
	vector<int> vec2; // 2 - 0 + e
	for (auto [u, e] : A[v]) {
		if (u == p)
			continue;
		auto [x, y, z] = dfs(u, v, e);
		vec0.push_back(y - x);
		vec2.push_back(z - x + e);
		sum += x;
	}
	vec0.push_back(0);
	sort(vec0.rbegin(), vec0.rend());
	sort(vec2.rbegin(), vec2.rend());
	int x = 0, y = 0, z = 0;
	if (vec2.size() >= 1 && p >= 0)
		x = sum + w + vec2[0];
	if (vec2.size() >= 2)
		z = sum + vec2[0] + vec2[1];
	y = max(x, z);
	x = max(x, sum);
	y = max(y, sum + vec0[0]);
	z = max(z, sum + vec0[0]);
	return {x, y, z};
}

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 << get<1>(dfs(0, -1, 0)) << '\n';
}

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