CP Lang
37 lines0.3 spec// coci21c4p4 Autobus... Centres: open k centres so every vertex is within the smallest possible
// distance of one. Binary search the distance; for a given limit, open centres greedily from the
// leaves up, only where a waiting vertex would otherwise fall out of range.
let (n, k) = read<(1..=200_000, 1..=200_000)>()
domain V = 1..=n
let g = Graph.undirected(read<[n - 1](u: V, v: V, w: 1..=1_000_000_000)>())
let t = Rooted(g, root: V.first!)
fn centres(limit: Int) -> List<V>:
var open: List<V> = []
// far: the farthest vertex below v still waiting for a centre; near: the nearest centre.
fn visit(v: V) -> (far: ?Int, near: ?Int):
var far = 0
var near: ?Int = None
for c in t.children(v):
let sub = visit(c)
let w = t.up_arc(c)!.w
near min= sub.near.map(d => d + w)
if let f = sub.far:
if f + w > limit:
open.push(c)
near min= w
else:
far max= f + w
if near.map(d => far + d <= limit) ?? false:
return (None, near)
(far, near)
if visit(t.root).far != None:
open.push(t.root)
open
let best = (0..=200_000_000_000_000).first_true(x => centres(x).len <= k)!
let chosen = centres(best)
let picked = V.mask(chosen)
let spare = V.filter(v => not picked[v]).take(k - chosen.len)
print(best)
print(chain(chosen, spare))
Accepted C++
112 lines · 36.82 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(...)
#endif
#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))
constexpr int maxn = 2e5 + 5;
long clim;
vector<int> ans;
vector<pair<int, int>> graph[maxn];
pair<long, long> dfs(int u, int p = -1) {
long mxbad = 0, mngood = 1e18;
for (auto& [v, w] : graph[u]) {
if (v == p) {
continue;
}
auto [nbad, ngood] = dfs(v, u);
mngood = min(mngood, ngood + w);
if (nbad == -1) {
continue;
}
if (nbad + w > clim) {
ans.push_back(v);
mngood = min(mngood, long(w));
} else {
mxbad = max(mxbad, w + nbad);
}
}
if (mxbad <= clim - mngood) {
return {-1, mngood};
}
return {mxbad, mngood};
}
void solve() {
int n, kv;
cin >> n >> kv;
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);
}
auto check = [&](long x) -> bool {
ans.clear();
clim = x;
if (dfs(0).first != -1) {
ans.push_back(0);
}
return sz(ans) <= kv;
};
long l = 0, r = 1e18;
while (l < r) {
long mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
check(l);
cout << l << endl;
dbg(sz(ans));
bool vis[n] {};
for (auto& a : ans) {
vis[a] = true;
}
for (int i = 0; i < n && sz(ans) < kv; i++) {
if (!vis[i]) {
ans.push_back(i);
}
}
for (int i = 0; i < kv; i++) {
cout << ans[i] + 1 << " \n"[i == kv - 1];
}
}
int main() {
cin.tie(nullptr);
cin.exceptions(ios::failbit);
ios_base::sync_with_stdio(false);
solve();
}