JOI 本選 2012 E - JOI 国のお祭り事情 (AOJ 0575, 難易度 10)

並列二分探索が想定ではなさそうだけど、並列二分探索法で解いてみました。

問題へのリンク

解法

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

struct UnionFind {
    vector<int> par, rank, sz;
    
    UnionFind(int n) : par(n), rank(n, 0), sz(n, 1) {
        for (int i = 0; i < n; ++i) par[i] = i;
    }
    void init(int n) {
        par.resize(n); rank.resize(n); sz.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, sz[i] = 1;
    }
    
    int root(int x) {
        if (par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    int size(int x) {
        return sz[root(x)];
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        sz[x] += sz[y];
        return true;
    }
};

typedef pair<int, int> Edge; // to, cost
typedef pair<int, int> pint;
const int INF = 1<<29;
vector<int> dist;

inline int calc(pint p) { return min(dist[p.first], dist[p.second]); }
inline bool cmp(pint p, pint q) { return calc(p) > calc(q); }

int main() {
    // Graph
    int N, M, K, Q; cin >> N >> M >> K >> Q;
    vector<vector<Edge> > G(N);
    vector<pint> edges;
    for (int i = 0; i < M; ++i) {
        int x, y, w; cin >> x >> y >> w; --x, --y;
        G[x].push_back(Edge(y, w));
        G[y].push_back(Edge(x, w));
        edges.push_back(pint(x, y));
    }
    
    // Dijkstra
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
    dist.assign(N, INF);
    for (int k = 0; k < K; ++k) {
        int fes; cin >> fes; --fes;
        dist[fes] = 0;
        que.push(pair<int,int>(0, fes));
    }
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;
        for (auto e : G[v]) {
            if (dist[e.first] > dist[v] + e.second) {
                dist[e.first] = dist[v] + e.second;
                que.push(make_pair(dist[e.first], e.first));
            }
        }
    }
    
    // queries
    vector<int> xs(Q), ys(Q);
    for (int q = 0; q < Q; ++q) {
        cin >> xs[q] >> ys[q];
        --xs[q], --ys[q];
    }
    
    // parallel binary search
    sort(edges.begin(), edges.end(), cmp);
    vector<int> left(Q, 0), right(Q, INF);
    UnionFind uf(N);
    while (true) {
        map<int, vector<int> > distToQueries;
        bool update = false;
        for (int q = 0; q < Q; ++q) {
            if (right[q] - left[q] > 1) {
                update = true;
                int mid = (left[q] + right[q]) / 2;
                distToQueries[-mid].push_back(q);
            }
        }
        if (!update) break;
        uf.init(N);
        int iter = 0;
        for (auto it = distToQueries.begin(); it != distToQueries.end(); ++it) {
            int mid = -(it->first);
            while (calc(edges[iter]) >= mid) {
                int u = edges[iter].first;
                int v = edges[iter].second;
                uf.merge(u, v);
                ++iter;
            }
            for (auto q : it->second) {
                if (!uf.issame(xs[q], ys[q])) right[q] = mid;
                else left[q] = mid;
            }
        }
    }
    for (int q = 0; q < Q; ++q) cout << left[q] << endl;
}