test/aoj0575_1.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-03-01 12:39:31+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575

Depends on

• data_structure/persistent_uf.cpp
• memo/macro.hpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575"
#include "../memo/macro.hpp"
#include "../data_structure/persistent_uf.cpp"

signed main(void) {
    ll n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<int> a(m), b(m), l(m);
    vector<vector<PII>> g(n);
    REP(i, m) {
        cin >> a[i] >> b[i] >> l[i];
        a[i]--, b[i]--;
        g[a[i]].push_back({b[i], l[i]});
        g[b[i]].push_back({a[i], l[i]});
    }
    vector<int> f(k);
    REP(i, k) cin >> f[i], f[i]--;
    vector<int> s(q), t(q);
    REP(i, q) cin >> s[i] >> t[i], s[i]--, t[i]--;

    vector<ll> dist(n, INF);
    priority_queue<PII, vector<PII>, greater<PII>> que;
    for(auto i: f) {
        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;
                que.push({dist[to.first], to.first});
            }
        }
    }

    vector<int> x(m);
    REP(i, m) x[i] = min(dist[a[i]], dist[b[i]]);
    vector<int> xs(x);
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), xs.end());
    vector<vector<int>> v(xs.size());
    REP(i, m) {
        x[i] = lower_bound(ALL(xs), x[i]) - xs.begin();
        v[x[i]].push_back(i);
    }

    // i番目の距離の辺まで追加した
    int idx = 0;
    persistentUnionFind uf(n);
    vector<persistentUnionFind> vuf(xs.size());
    for(int i=(int)xs.size()-1; i>=0; --i) {
        for(auto j: v[i]) {
            uf.unite(a[j], b[j]);
        }
        vuf[idx++] = uf;
    }

    REP(i, q) {
        // [mid,xs.size()) の辺を追加したときにs[i]とt[i]が連結か
        auto check = [&](ll mid) { return vuf[xs.size()-1-mid].same(s[i], t[i]); };
        ll lb=0, ub = xs.size();
        while(ub-lb > 1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) lb = mid;
            else ub = mid;
        }
        cout << xs[lb] << endl;
    }

    return 0;
}

#line 1 "test/aoj0575_1.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575"
#line 1 "memo/macro.hpp"
#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;
const ll INF = 1LL<<60;
#line 1 "data_structure/persistent_uf.cpp"
// BEGIN CUT
template<typename T, int B = 3>
class persistentArray {
private:
    struct node {
        node *ch[1<<B] = {};
        T val = -1;

        node() {}
        node(const T &v) : val(v) {}
    };

    node *root;

    node* build(node *x, const T &dat, int a) {
        if(!x) x = new node();
        if(a == 0) {
            x->val = dat;
            return x;
        }
        auto p = build(x->ch[a&((1<<B)-1)], dat, a>>B);
        x->ch[a&((1<<B)-1)] = p;
        return x;
    }
    pair<node*, T*> mutable_get(node* x, int a) {
        x = x ? new node(*x) : new node();
        if(a == 0) return {x, &x->val};
        auto p = mutable_get(x->ch[a&((1<<B)-1)], a >> B);
        x->ch[a&((1<<B)-1)] = p.first;
        return make_pair(x, p.second);
    }
    T immutable_get(int a, node* x) {
        if(a == 0) return x->val;
        return immutable_get(a>>B, x->ch[a & ((1<<B)-1)]);
    }
public:
    persistentArray() : root(nullptr) {}

    void build(const vector<T> &v) {
        for(int i=0; i<(int)v.size(); ++i) {
            root = build(root, v[i], i);
        }
    }

    T *mutable_get(const int &k) {
        auto p = mutable_get(root, k);
        root = p.first;
        return p.second;
    }
    T operator[](int k) {
        return immutable_get(k, root);
    }
};

struct persistentUnionFind {
    persistentArray<int> data;

    persistentUnionFind() {}
    persistentUnionFind(int sz) { data.build(vector<int>(sz, -1)); }

    int find(int k) {
        int p = data[k];
        return p >= 0 ? find(p) : k;
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return;
        auto u = data[x];
        auto v = data[y];
        if(u < v) {
            auto a = data.mutable_get(x); *a += v;
            auto b = data.mutable_get(y); *b = x;
        } else {
            auto a = data.mutable_get(y); *a += u;
            auto b = data.mutable_get(x); *b = y;
        }
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return -data[find(x)]; }
};
// END CUT
#line 4 "test/aoj0575_1.test.cpp"

signed main(void) {
    ll n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<int> a(m), b(m), l(m);
    vector<vector<PII>> g(n);
    REP(i, m) {
        cin >> a[i] >> b[i] >> l[i];
        a[i]--, b[i]--;
        g[a[i]].push_back({b[i], l[i]});
        g[b[i]].push_back({a[i], l[i]});
    }
    vector<int> f(k);
    REP(i, k) cin >> f[i], f[i]--;
    vector<int> s(q), t(q);
    REP(i, q) cin >> s[i] >> t[i], s[i]--, t[i]--;

    vector<ll> dist(n, INF);
    priority_queue<PII, vector<PII>, greater<PII>> que;
    for(auto i: f) {
        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;
                que.push({dist[to.first], to.first});
            }
        }
    }

    vector<int> x(m);
    REP(i, m) x[i] = min(dist[a[i]], dist[b[i]]);
    vector<int> xs(x);
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), xs.end());
    vector<vector<int>> v(xs.size());
    REP(i, m) {
        x[i] = lower_bound(ALL(xs), x[i]) - xs.begin();
        v[x[i]].push_back(i);
    }

    // i番目の距離の辺まで追加した
    int idx = 0;
    persistentUnionFind uf(n);
    vector<persistentUnionFind> vuf(xs.size());
    for(int i=(int)xs.size()-1; i>=0; --i) {
        for(auto j: v[i]) {
            uf.unite(a[j], b[j]);
        }
        vuf[idx++] = uf;
    }

    REP(i, q) {
        // [mid,xs.size()) の辺を追加したときにs[i]とt[i]が連結か
        auto check = [&](ll mid) { return vuf[xs.size()-1-mid].same(s[i], t[i]); };
        ll lb=0, ub = xs.size();
        while(ub-lb > 1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) lb = mid;
            else ub = mid;
        }
        cout << xs[lb] << endl;
    }

    return 0;
}

Back to top page