Submission #265554

#	Time	Username	Problem	Language	Result	Execution time	Memory
265554		square1001	Beads and wires (APIO14_beads)	C++14	100 / 100	172 ms	23408 KiB

beads

// APIO 2014 Problem 3 - Beads and Wires

#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
const int inf = 2012345678;
int main() {
	// step #1. read input
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> ga(N - 1), gb(N - 1), gw(N - 1);
	for(int i = 0; i < N - 1; ++i) {
		cin >> ga[i] >> gb[i] >> gw[i];
		--ga[i], --gb[i];
	}
	// step #2. construct a graph
	vector<int> sep(N + 1);
	for(int i = 0; i < N - 1; ++i) {
		++sep[ga[i] + 1];
		++sep[gb[i] + 1];
	}
	for(int i = 0; i < N; ++i) {
		sep[i + 1] += sep[i];
	}
	vector<int> ctr(sep);
	vector<int> to(2 * N - 2), cost(2 * N - 2);
	for(int i = 0; i < N - 1; ++i) {
		to[ctr[ga[i]]] = gb[i]; cost[ctr[ga[i]]++] = gw[i];
		to[ctr[gb[i]]] = ga[i]; cost[ctr[gb[i]]++] = gw[i];
	}
	// step #3. calculation (zenhoui-tree-dp part 1)
	vector<int> par(N);
	vector<pair<int, int> > dp1(N);
	function<void(int, int)> solve1 = [&](int pos, int pre) {
		// returns = (no mid-blue, one mid-blue)
		par[pos] = pre;
		int sumcost = 0, delta = -inf;
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) continue;
			solve1(to[i], pos);
			sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
			delta = max(delta, min(dp1[to[i]].first - dp1[to[i]].second, cost[i]));
		}
		dp1[pos] = make_pair(sumcost, sumcost + delta);
	};
	solve1(0, -1);
	// step #4. calculation (zenhoui-tree-dp part 2)
	vector<pair<int, int> > dp2(N);
	function<void(int, int)> solve2 = [&](int pos, int pre) {
		int sumcost = 0;
		vector<pair<int, int> > deltas;
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) {
				sumcost += max(dp2[pos].first, dp2[pos].second + cost[i]);
				deltas.push_back(make_pair(min(dp2[pos].first - dp2[pos].second, cost[i]), -1));
			}
			else {
				sumcost += max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
				deltas.push_back(make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i));
			}
		}
		sort(deltas.begin(), deltas.end(), greater<pair<int, int> >());
		for(int i = sep[pos]; i < sep[pos + 1]; ++i) {
			if(to[i] == pre) continue;
			pair<int, int> dm = make_pair(min(dp1[to[i]].first - dp1[to[i]].second, cost[i]), i);
			int sc = sumcost - max(dp1[to[i]].first, dp1[to[i]].second + cost[i]);
			dp2[to[i]] = make_pair(sc, sc + (dm != deltas[0] ? deltas[0].first : (deltas.size() != 1 ? deltas[1].first : -inf)));
			solve2(to[i], pos);
		}
	};
	dp2[0] = make_pair(0, -inf);
	solve2(0, -1);
	// step #5. calculate and print the answer
	int ans = 0;
	for(int i = 0; i < N; ++i) {
		int sumcost = 0;
		for(int j = sep[i]; j < sep[i + 1]; ++j) {
			if(to[j] == par[i]) {
				sumcost += max(dp2[i].first, dp2[i].second + cost[j]);
			}
			else {
				sumcost += max(dp1[to[j]].first, dp1[to[j]].second + cost[j]);
			}
		}
		ans = max(ans, sumcost);
	}
	cout << ans << endl;
	return 0;
}

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