제출 #1326805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326805		kawhiet	Evacuation plan (IZhO18_plan)	C++20	41 / 100	4091 ms	24192 KiB

plan

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p;

    DSU(int n) {
        p.assign(n + 1, -1);
    }

    int root(int x) { return (p[x] == -1 ? x : (p[x] = root(p[x]))); }

    bool link(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        p[y] = x;
        return true;
    }
};

constexpr int N = 1e5 + 1;
constexpr int inf = 1e9;

int dist[N];
vector<array<int, 2>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> e;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back({u, v});
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    fill(dist, dist + N, inf);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int u;
        cin >> u;
        dist[u] = 0;
        q.emplace(0, u);
    }
    while (!q.empty()) {
        auto [s, u] = q.top();
        q.pop();
        if (dist[u] < s) continue;
        for (auto [v, w] : g[u]) {
            if (s + w < dist[v]) {
                dist[v] = s + w;
                q.emplace(s + w, v);
            }
        }
    }
    int query;
    cin >> query;
    while (query--) {
        int s, t;
        cin >> s >> t;
        int l = 0, r = inf;
        while (l + 1 < r) {
            int tm = (l + r) / 2;
            vector<bool> is(n + 1);
            for (int i = 1; i <= n; i++) {
                if (dist[i] >= tm) {
                    is[i] = 1;
                }
            }
            DSU dsu(n + 1);
            for (auto [u, v] : e) {
                if (is[u] && is[v]) {
                    dsu.link(u, v);
                }
            }
            if (dsu.root(s) == dsu.root(t)) {
                l = tm;
            } else {
                r = tm;
            }
        }
        cout << l << '\n';
    }
    return 0;
}

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