← Real problems

coci21c4p4

hardtreebinary-searchgreedyStatement on DMOJ

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();
}