제출 #1365206

#제출 시각아이디문제언어결과실행 시간메모리
1365206Ahmed_bahyEvacuation plan (IZhO18_plan)C++20
100 / 100
451 ms85416 KiB
#include <bits/stdc++.h>
#define int  long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;

const int N = 1e5 + 10, inf = 1e9 + 10;

struct DSU
{
    vector<int> p, rnk;
    DSU(int n) { p = vector<int>(n + 1, -1); rnk = vector<int>(n + 1, 0); }
    int size(int x) { return -p[find_set(x)]; }
    bool sameSet(int a, int b) { return find_set(a) == find_set(b); }
    int find_set(int x) { return (p[x] < 0) ? x : p[x] = find_set(p[x]); }
    bool union_set(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if (a == b) return false;
        if (rnk[b] > rnk[a]) swap(a, b);
        rnk[a] += (rnk[a] == rnk[b]);
        p[a] += p[b];
        p[b] = a;
        return true;
    }
};

void solve() {
    int n, m; cin >> n >> m;
    vector<array<int, 3>> edges(m);
    vector<vector<array<int, 2>>> adj(n);
    for(auto &[x, y, w]: edges){
        cin >> x >> y >> w;
        x--; y--;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }

    int k; cin >> k;
    vector<int> banned(k);
    vector<bool> is_banned(n);
    for(auto &i: banned)cin >> i, i--, is_banned[i] = 1;

    int q; cin >> q;
    vector<array<int, 2>> qu(q);
    for(auto &[x, y]: qu)cin >> x >> y, x--, y--;

    DSU dsu(n);
    for(auto &[u, v, w]: edges)
        if(!is_banned[u] && !is_banned[v])dsu.union_set(u, v);

    priority_queue<array<int, 2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    vector<int> dist(n, inf);
    for(auto &i: banned){
        pq.push({0, i});
        dist[i] = 0;
    }

    while(!pq.empty()){
        auto [w, cur] = pq.top(); pq.pop();
        if(w != dist[cur])continue;
        for(auto &[i,  w]: adj[cur]){
            if(dist[i] > dist[cur] + w){
                dist[i] = dist[cur] + w;
                pq.push({dist[i], i});
            }
        }
    }

    vector<array<int, 3>> new_edges;
    for(auto &[u, v, w]: edges){
        new_edges.push_back({min(dist[u], dist[v]), u, v});
    }

    sort(rall(new_edges));

    int sz = new_edges.size();
    vector<int> l(q, 0), r(q, sz - 1), ans(q, -1);
    while(true){
        bool stop = true;
        vector<vector<int>> mid(sz);
        for(int i = 0; i < q; i++){
            if(l[i] > r[i])continue;
            int md = (l[i] + r[i]) / 2;
            mid[md].push_back(i);
            stop = false;
        }

        if(stop)break;

        DSU dsu2(n);
        for(int i = 0; i < sz; i++){
            auto [w, u, v] = new_edges[i];
            dsu2.union_set(u, v);
            for(auto &ind: mid[i]){
                auto [x, y] = qu[ind];
                if(!dsu.sameSet(x, y)){
                    ans[ind] = 0;
                    l[ind] = r[ind] + 1;
                }else if(dsu2.sameSet(x, y)){
                    ans[ind] = w;
                    r[ind] = i - 1;
                }else l[ind] = i + 1;
            }
        }
    }

    for(auto &i: ans)cout << i << "\n";
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…