Submission #734198

#	Time	Username	Problem	Language	Result	Execution time	Memory
734198		SanguineChameleon	Beads and wires (APIO14_beads)	C++17	100 / 100	354 ms	43920 KiB

beads

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxN = 2e5 + 20;
vector<pair<int, int>> adj[maxN];
int par_w[maxN];
int dp[maxN][2];
int tot[maxN];
multiset<int> gain[maxN];
int res;

void dfs1(int u, int p) {
	tot[u] = 0;
	gain[u].clear();
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != p) {
			par_w[v] = w;
			dfs1(v, u);
			tot[u] += max(dp[v][0], dp[v][1]);
			gain[u].insert(w + dp[v][0] - max(dp[v][0], dp[v][1]));
		}
	}
	dp[u][0] = tot[u];
	dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);
}

void dfs2(int u, int p) {
	res = max(res, dp[u][0]);
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != p) {
			par_w[u] = w;
			par_w[v] = 0;

			tot[u] -= max(dp[v][0], dp[v][1]);
			gain[u].erase(gain[u].find(w + dp[v][0] - max(dp[v][0], dp[v][1])));

			dp[u][0] = tot[u];
			dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);

			tot[v] += max(dp[u][0], dp[u][1]);
			gain[v].insert(w + dp[u][0] - max(dp[u][0], dp[u][1]));

			dp[v][0] = tot[v];
			dp[v][1] = tot[v] + (!gain[v].empty() ? *gain[v].rbegin() + par_w[v] : 0);

			dfs2(v, u);

			par_w[u] = 0;
			par_w[v] = w;

			gain[v].erase(gain[v].find(w + dp[u][0] - max(dp[u][0], dp[u][1])));
			tot[v] -= max(dp[u][0], dp[u][1]);

			dp[v][0] = tot[v];
			dp[v][1] = tot[v] + (!gain[v].empty() ? *gain[v].rbegin() + par_w[v] : 0);

			tot[u] += max(dp[v][0], dp[v][1]);
			gain[u].insert(w + dp[v][0] - max(dp[v][0], dp[v][1]));

			dp[u][0] = tot[u];
			dp[u][1] = tot[u] + (!gain[u].empty() ? *gain[u].rbegin() + par_w[u] : 0);
		}
	}
}

void just_do_it() {
	int n;
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	dfs1(1, -1);
	dfs2(1, -1);
	cout << res;
}

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