Submission #47903

#	Time	Username	Problem	Language	Result	Execution time	Memory
47903		square1001	Beads and wires (APIO14_beads)	C++14	0 / 100	10 ms	4992 KiB

beads

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 2012345678;
struct edge {
	int to, cost;
	edge() : to(-1), cost(0) {};
	edge(int to_, int cost_) : to(to_), cost(cost_) {};
};
int n, dp[200009][2]; vector<edge> g[200009];
pair<int, int> solve(int pos, int pre) {
	if (pre != -1) {
		int sum = 0, mx = -inf;
		for (edge e : g[pos]) {
			if (e.to == pre) continue;
			pair<int, int> res = solve(e.to, pos);
			sum += max(res.first, res.second + e.cost);
			if (res.first > res.second + e.cost) {
				mx = max(mx, e.cost);
			}
			else {
				mx = max(mx, res.first - res.second);
			}
		}
		return make_pair(sum, sum + mx);
	}
	int sum = 0, mx1 = -inf, mx2 = -inf;
	for (edge e : g[pos]) {
		pair<int, int> res = solve(e.to, pos);
		sum += max(res.first, res.second + e.cost);
		int d = (res.first > res.second ? e.cost : res.first - res.second);
		if (d > mx1) {
			mx2 = mx1;
			mx1 = d;
		}
		else if (d > mx2) {
			mx2 = d;
		}
	}
	return make_pair(sum + mx1 + mx2, -inf);
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int a, b, c;
		cin >> a >> b >> c; a--, b--;
		g[a].push_back(edge(b, c));
		g[b].push_back(edge(a, c));
	}
	int ret = 0;
	for (int i = 0; i < n; i++) {
		if (g[i].size() <= 1) continue;
		pair<int, int> res = solve(i, -1);
		ret = max(ret, res.first);
	}
	cout << ret << '\n';
	return 0;
}

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