Submission #261192

#	Time	Username	Problem	Language	Result	Execution time	Memory
261192		atoiz	Beads and wires (APIO14_beads)	C++14	100 / 100	322 ms	27632 KiB

beads

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200007;
const int64_t INF = 1e13;
int64_t dp[MAXN][2][2];
int N;
vector<pair<int, int>> G[MAXN];

void solve(int u, int p, int64_t c)
{
	dp[u][0][0] = dp[u][0][1] = -INF;
	dp[u][1][0] = dp[u][1][1] = -INF;

	int64_t a[2][2] = {{0, -INF}, {-INF, -INF}}; // --
	int64_t b[3] = {0, -INF, -INF}; // -0
	int64_t f[2] = {0, -INF};
	for (auto e : G[u]) {
		int v = e.first, w = e.second;
		if (v == p) continue;
		solve(v, u, w);

		a[1][1] = max(a[1][1] + dp[v][0][0], max(a[1][0] + dp[v][1][1], a[0][1] + dp[v][1][0]) + w);
		a[0][1] = max(a[0][1] + dp[v][0][0], a[0][0] + dp[v][1][1] + w);
		a[1][0] = max(a[1][0] + dp[v][0][0], a[0][0] + dp[v][1][0] + w);
		a[0][0] += dp[v][0][0];

		b[1] = max(b[1] + dp[v][0][0], b[0] + dp[v][1][0] + w);
		b[2] = max(b[2] + dp[v][0][0], b[0] + dp[v][1][1] + w);
		b[0] += dp[v][0][0];

		f[1] = max(f[0] + dp[v][0][1], f[1] + dp[v][0][0]);
		f[0] += dp[v][0][0];
	}

	dp[u][1][1] = max(dp[u][1][1], a[1][1]);
	dp[u][0][0] = max(dp[u][0][0], b[1] + c);
	dp[u][0][1] = max(dp[u][0][1], b[2] + c);

	dp[u][1][0] = max(dp[u][1][0], b[0]);
	dp[u][1][1] = max(dp[u][1][1], b[0]);
	dp[u][1][1] = max(dp[u][1][1], f[1]);

	dp[u][0][0] = max(dp[u][0][0], dp[u][1][0]);
	dp[u][0][1] = max(dp[u][0][1], dp[u][1][1]);

	// cout << u << ' ' << 0 << ' ' << 0 << ": " << dp[u][0][0] << endl;
	// cout << u << ' ' << 0 << ' ' << 1 << ": " << dp[u][0][1] << endl;
	// cout << u << ' ' << 1 << ' ' << 0 << ": " << dp[u][1][0] << endl;
	// cout << u << ' ' << 1 << ' ' << 1 << ": " << dp[u][1][1] << endl;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].emplace_back(v, w);
		G[v].emplace_back(u, w);
	}
	solve(1, 0, -INF);
	cout << dp[1][0][1] << endl;
}

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