Codeforces Round #600 (Div. 2) F - Cheap Robot

問題ページ
ボロノイMSTの要領でcentralが頂点となっていて辺の重みが元のグラフのcentral間の最短距離であるようなグラフを構成する．
capacityが のときにクエリ を達成可能か？ グラフで と のパスの重みのmaxが以下 となる． を決め打つと，使用できる辺が決まる．このときに と が連結であれば容量が 以上のとき達成可能である． について二分探索をすれば，各クエリについて で答えがわかる．
あとは並列二分探索や永続union-findなどを使うことでグラフを複数回構築している部分をまとめることができ，十分高速に答えを求められる．

以下のコードは部分永続UFを使ったもの

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
// find:O(logN) unite:O(logN)  
struct partialPersistentUF {  
    const static int MAX_N = 100010;  
    unordered_map<int, int> par[MAX_N];  
    int rank[MAX_N];  
    int fin[MAX_N];  
    int idx;  
    partialPersistentUF() { init(); }  
    partialPersistentUF(int n) { init(n); }  
    void init(int n=MAX_N) {  
        idx = 0;  
        REP(i, n) par[i][0] = i, rank[i] = 1, fin[i] = 0;  
    }  
    // t(1-indexed)回目までのuniteでのxの親  
    int find(int x, int t) {  
        if(t >= fin[x] && par[x][fin[x]] != x) return find(par[x][fin[x]], t);  
        return x;  
    }  
    void unite(int x, int y) {  
        x = find(x, idx);  
        y = find(y, idx);  
        idx++;  
        if(x == y) return;  
        if(rank[x] < rank[y]) par[x][idx] = y, fin[x] = idx;  
        else {  
          par[y][idx] = x, fin[y] = idx;  
          if(rank[x] == rank[y]) rank[x]++;  
        }  
    }  
    bool same(int x, int y, int t) { return find(x, t) == find(y, t); }  
};  
  
int main(void) {  
    ll n, m, k, q;  
    cin >> n >> m >> k >> q;  
    vector<vector<PII>> g(n);  
    REP(i, m) {  
        ll a, b, c;  
        cin >> a >> b >> c;  
        a--, b--;  
        g[a].push_back({b, c});  
        g[b].push_back({a, c});  
    }  
  
    // central から dijkstra  
    vector<ll> col(n, -1), dist(n, INF);  
    priority_queue<PII, vector<PII>, greater<PII>> que;  
    REP(i, k) {  
        col[i] = i;  
        dist[i] = 0;  
        que.push({0, i});  
    }  
    while(que.size()) {  
        PII p = que.top(); que.pop();  
        if(dist[p.second] < p.first) continue;  
        for(auto to: g[p.second]) {  
            if(dist[to.first] > dist[p.second] + to.second) {  
                dist[to.first] = dist[p.second] + to.second;  
                col[to.first] = col[p.second];  
                que.push({dist[to.first], to.first});  
            }  
        }  
    }  
    // 重み dist[i]+dist[to.first]+to.second で col[i] と col[to.first] を結ぶ辺
    map<ll, vector<PII>> mp;  
    REP(i, n) for(auto to: g[i]) {  
        if(i < to.first && col[i] != col[to.first]) {  
            mp[dist[i]+dist[to.first]+to.second].push_back({col[i], col[to.first]});  
        }  
    }  
    // UFの処理  
    ll sz = 0;  
    vector<ll> ts, ope;  
    partialPersistentUF uf(k);  
    for(auto i: mp) {  
        ts.push_back(i.first);  
        for(auto j: i.second) uf.unite(j.first, j.second);  
        sz += i.second.size();  
        ope.push_back(sz);  
    }  
  
    while(q--) {  
        ll a, b;  
        cin >> a >> b;  
        a--, b--;  
  
        ll lb = -1, ub = (ll)ts.size()-1;  
        while(ub - lb > 1) {  
            ll mid = (lb+ub)/2;  
            if(uf.same(a, b, ope[mid])) ub = mid;  
            else lb = mid;  
        }  
        cout << ts[ub] << '\n';  
    }  
  
    return 0;  
}