test/aoj0575_0.test.cpp

Back to top page

• category: test
• View this file on GitHub
  • Last commit date: 2020-05-20 15:35:38+09:00
• see: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0575

Depends on

• data_structure/partial_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/partial_persistent_uf.cpp"

signed main(void) {
    ll n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<ll> 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<ll> f(k);
    REP(i, k) cin >> f[i], f[i]--;
    vector<ll> 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<ll> x(m);
    REP(i, m) x[i] = min(dist[a[i]], dist[b[i]]);
    vector<ll> xs(x);
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), xs.end());
    vector<vector<ll>> v(xs.size());
    REP(i, m) {
        x[i] = lower_bound(ALL(xs), x[i]) - xs.begin();
        v[x[i]].push_back(i);
    }

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

    REP(i, q) {
        // [mid,xs.size()) の辺を追加したときにs[i]とt[i]が連結か
        auto check = [&](ll mid) { return uf.same(s[i], t[i], trans[mid]); };
        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_0.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/partial_persistent_uf.cpp"
// BEGIN CUT
struct partial_persistent_uf {
    int now;
    vector<int> time, par, rank;
    vector<vector<PII>> sz;
    partial_persistent_uf(int n) : now(0), time(n, 1<<30), par(n, 1), sz(n, vector<PII>({{0,1}})) {}
    // t(1-indexed) 回目までuniteしたときのxの根
    int find(int x, int t) {
        if(time[x] > t) return x;
        return find(par[x], t);
    }
    int unite(int x, int y) {
        ++now;
        x = find(x, now), y = find(y, now);
        if(x == y) return now;
        if(par[x] < par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        time[y] = now;
        sz[x].emplace_back(now, par[x]);
        return now;
    }
    bool same(int x, int y, int t) { 
        return find(x, t) == find(y, t);
    }
    int size(int x, int t) { 
        x = find(x, t);
        return prev(upper_bound(ALL(sz[x]), PII(t, INF)))->second; 
    }
};
// END CUT
#line 4 "test/aoj0575_0.test.cpp"

signed main(void) {
    ll n, m, k, q;
    cin >> n >> m >> k >> q;
    vector<ll> 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<ll> f(k);
    REP(i, k) cin >> f[i], f[i]--;
    vector<ll> 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<ll> x(m);
    REP(i, m) x[i] = min(dist[a[i]], dist[b[i]]);
    vector<ll> xs(x);
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), xs.end());
    vector<vector<ll>> v(xs.size());
    REP(i, m) {
        x[i] = lower_bound(ALL(xs), x[i]) - xs.begin();
        v[x[i]].push_back(i);
    }

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

    REP(i, q) {
        // [mid,xs.size()) の辺を追加したときにs[i]とt[i]が連結か
        auto check = [&](ll mid) { return uf.same(s[i], t[i], trans[mid]); };
        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