제출 #625066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
625066		KoD	Evacuation plan (IZhO18_plan)	C++17	100 / 100	472 ms	40452 KiB

plan

#include <bits/stdc++.h>

using ll = long long;
using std::vector;
using std::array;
using std::pair;
using std::tuple;

constexpr int inf = (1 << 30) - 1;

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<>>;

class union_find {
    vector<int> par, time;
    int stamp = 0;

  public:
    explicit union_find(const int n) : par(n, -1), time(n, inf) {}

    int find(const int u, const int t) const {
        if (time[u] < t) {
            return find(par[u], t);
        } else {
            return u;
        }
    }

    void merge(int x, int y) {
        x = find(x, stamp);
        y = find(y, stamp);
        if (x != y) {
            if (par[x] > par[y]) {
                std::swap(x, y);
            }
            par[x] += par[y];
            par[y] = x;
            time[y] = stamp;
        }
        stamp += 1;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, M;
    std::cin >> N >> M;
    vector<int> S(M), T(M), C(M);
    vector<vector<pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        std::cin >> S[i] >> T[i] >> C[i];
        S[i] -= 1;
        T[i] -= 1;
        graph[S[i]].emplace_back(T[i], C[i]);
        graph[T[i]].emplace_back(S[i], C[i]);
    }
    vector<int> dist(N, inf);
    min_heap<pair<int, int>> heap;
    const auto push = [&](const int u, const int d) {
        if (dist[u] > d) {
            dist[u] = d;
            heap.emplace(d, u);
        }
    };
    int K;
    std::cin >> K;
    while (K--) {
        int u;
        std::cin >> u;
        u -= 1;
        push(u, 0);
    }
    while (!heap.empty()) {
        const auto [d, u] = heap.top();
        heap.pop();
        if (d > dist[u]) {
            continue;
        }
        for (const auto& [v, c] : graph[u]) {
            push(v, d + c);
        }
    }
    vector<tuple<int, int, int>> edges(M);
    for (int i = 0; i < M; ++i) {
        edges[i] = {std::min(dist[S[i]], dist[T[i]]), S[i], T[i]};
    }
    std::sort(edges.rbegin(), edges.rend());
    union_find dsu(N);
    for (const auto& [x, u, v] : edges) {
        dsu.merge(u, v);
    }
    int Q;
    std::cin >> Q;
    while (Q--) {
        int u, v;
        std::cin >> u >> v;
        u -= 1, v -= 1;
        int ok = M, ng = 0;
        while (ok - ng > 1) {
            const int md = (ok + ng) / 2;
            (dsu.find(u, md) == dsu.find(v, md) ? ok : ng) = md;
        }
        std::cout << std::get<0>(edges[ok - 1]) << '\n';
    }
    return 0;
}

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