Submission #1112642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112642		MisterReaper	Evacuation plan (IZhO18_plan)	C++17	100 / 100	689 ms	33716 KiB

plan

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "../../../debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int INF = int(1E9);
constexpr int max_N = int(1E5) + 5;

bool chmin(int& a, int b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

int N, M;
std::vector<std::pair<int, int>> adj[max_N];
std::vector<int> dist;

struct DSU {
    std::vector<int> f, siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.assign(n, 0);
        siz.assign(n, 1);
        std::iota(f.begin(), f.end(), 0);
    }

    int get(int x) {
        while (f[x] != x) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) {
            return false;
        } else if (siz[a] > siz[b]) {
            std::swap(a, b);
        }
        f[a] = b;
        siz[b] += siz[a];
        return true;
    }
    bool same(int a, int b) {
        return get(a) == get(b);
    }
    int size(int x) {
        return siz[get(x)];
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int A, B, C;
        std::cin >> A >> B >> C;
        --A, --B;
        adj[A].emplace_back(B, C);
        adj[B].emplace_back(A, C);
    }

    dist.assign(N, INF);
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    int K;
    std::cin >> K;
    for (int i = 0, x; i < K; ++i) {
        std::cin >> x;
        --x;
        pq.emplace(dist[x] = 0, x);
    }

    while (!pq.empty()) {
        auto[d, v] = pq.top();
        pq.pop();
        if (dist[v] != d) {
            continue;
        }
        for (auto[u, w] : adj[v]) {
            if (chmin(dist[u], d + w)) {
                pq.emplace(dist[u], u);
            }
        }
    }

    debug(dist);

    int Q;
    std::cin >> Q;
    
    std::vector<int> ans(Q);
    std::vector<std::pair<int, int>> qq(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> qq[i].first >> qq[i].second;
        --qq[i].first, --qq[i].second;
    }

    std::vector<std::tuple<int, int, int>> pv(Q);
    for (int i = 0; i < Q; ++i) {
        pv[i] = {0, INF, i};
    }

    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::sort(ord.begin(), ord.end(), [&](auto lhs, auto rhs) {
        return dist[lhs] > dist[rhs];
    });

    DSU dsu;
    std::vector<int> act;
    for (int i = 0; i < 31; ++i) {
        std::sort(pv.rbegin(), pv.rend());

        int cur = 0;
        dsu.init(N);
        act.assign(N, false);
        auto work = [&](int x) -> void {
            while (cur < N && dist[ord[cur]] >= x) {
                int v = ord[cur];
                act[v] = true;
                for (auto[u, w] : adj[v]) {
                    if (act[u]) {
                        dsu.unite(u, v);
                    }
                }
                ++cur;
            }
        };

        std::vector<std::tuple<int, int, int>> new_pv;
        for (auto[lo, hi, idx] : pv) {
            if (lo == hi) {
                ans[idx] = lo;
                continue;
            }
            int mid = (lo + hi) >> 1;
            work(mid);
            if (!dsu.same(qq[idx].first, qq[idx].second)) {
                new_pv.emplace_back(lo, mid, idx);
            } else {
                new_pv.emplace_back(mid + 1, hi, idx);
            }
        }

        pv.swap(new_pv);
    }

    for (int i = 0; i < Q; ++i) {
        std::cout << ans[i] - 1 << '\n';
    }

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46