← Real problems

noip18p3

hardbinary-searchtree-dpgreedyStatement on DMOJ

CP Lang

24 lines0.3 spec
// noip18p3 Track Construction: build m edge-disjoint paths in a weighted tree, making the shortest
// as long as possible. Binary search the length k. Going up, each vertex pairs the chains its
// children hand it into tracks of length at least k (the shortest chain takes the shortest
// partner that completes it) and passes the longest unpaired chain to its parent.
let (n, m) = read<(2..=5e4, 1..=5e4)>()
domain V = 1..=n
let t = Rooted(Graph.undirected(read<[n - 1](u: V, v: V, w: 1..=1e4)>()), root: V.first!)

fn tracks(k: Int) -> Int:
    var made = 0
    fn up(v: V) -> Int:
        var chains = SortedBag.of(List(t.child_arcs(v).map(a => up(a.to) + a.w)))
        made += chains.drain_range(k..).count()
        var spare = 0
        while let x = chains.pop_first():
            if chains.take_first(y => x + y >= k) is Some(_):
                made += 1
            else:
                spare = x
        spare
    up(t.root)
    made

print((1..=5e8).last_true(k => tracks(k) >= m)!)

Accepted C++

122 lines · 1.33 s on the judge
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
	cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
	cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
		 << ": ";                                          \
	dbgh(__VA_ARGS__)
#else
#define cerr   \
	if (false) \
	cerr
#define dbg(...) 1412
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int maxn = 5e4;

vector<pair<int, int>> graph[maxn];

void pdfs(int u) {
	for (auto& [v, w] : graph[u]) {
		graph[v].erase(
			find(begin(graph[v]), end(graph[v]), pair<int, int> {u, w}));
		pdfs(v);
	}
}

struct Solver {
	int k, ans = -1;

	explicit Solver(int k) : k(k) {}

	int dfs(int u) {
		multiset<int> vals;
		for (auto& [v, w] : graph[u]) {
			int cur = dfs(v) + w;
			if (cur < k) {
				vals.insert(cur);
			} else {
				ans++;
			}
		}
		int ret = 0;
		while(sz(vals)) {
			int cur = *vals.begin();
			vals.erase(vals.begin());
			auto it = vals.lower_bound(k - cur);
			if (it != vals.end()) {
				vals.erase(it);
				ans++;
			} else {
				ret = cur;
			}
		}
		return ret;
	}

	int solve() {
		if (ans == -1) {
			ans = 0;
			dfs(0);
		}
		return ans;
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n - 1; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u--;
		v--;
		graph[u].emplace_back(v, w);
		graph[v].emplace_back(u, w);
	}
	pdfs(0);
	int l = 0, r = 1e9;
	while (l < r) {
		int mid = (l + r + 1) / 2;
		Solver s(mid);
		if (s.solve() >= m) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	cout << l << endl;
}

int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
	// cin >> t;
	for (int _ = 1; _ <= t; _++) {
		dbg(_);
		// cout << "Case #" << _ << ": ";
		solve();
	}
}