제출 #600476

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600476		stevancv	Evacuation plan (IZhO18_plan)	C++14	100 / 100	567 ms	47108 KiB

plan

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 3e3 + 2;
const int mod = 1e9 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(m), b(m), c(m);
    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i] -= 1; b[i] -= 1;
        g[a[i]].push_back({b[i], c[i]});
        g[b[i]].push_back({a[i], c[i]});
    }
    int k; cin >> k;
    priority_queue<array<int, 2>> pq;
    vector<int> dist(n, 1e9);
    for (int i = 0; i < k; i++) {
        int x; cin >> x; x -= 1;
        pq.push({0, x});
        dist[x] = 0;
    }
    while (!pq.empty()) {
        auto s = pq.top();
        pq.pop();
        s[0] *= -1;
        if (s[0] != dist[s[1]]) continue;
        for (auto u : g[s[1]]) {
            if (dist[u[0]] > dist[s[1]] + u[1]) {
                dist[u[0]] = dist[s[1]] + u[1];
                pq.push({-dist[u[0]], u[0]});
            }
        }
    }
    int q; cin >> q;
    vector<vector<array<int, 2>>> qq(n);
    for (int i = 0; i < q; i++) {
        int S, T; cin >> S >> T;
        S -= 1; T -= 1;
        qq[S].push_back({T, i});
        qq[T].push_back({S, i});
    }
    vector<array<int, 3>> all;
    for (int i = 0; i < m; i++) {
        all.push_back({min(dist[a[i]], dist[b[i]]), a[i], b[i]});
    }
    sort(all.rbegin(), all.rend());
    vector<int> ans(q);
    vector<int> p(n), sz(n);
    for (int i = 0; i < n; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    function<int(int)> Find = [&] (int x) {
        if (x == p[x]) return x;
        return p[x] = Find(p[x]);
    };
    int cuv = 1e9;
    function<void(int, int)> Unite = [&] (int x, int y) {
        x = Find(x); y = Find(y);
        if (x == y) return;
        if (sz[x] < sz[y]) swap(x, y);
        for (auto u : qq[y]) {
            if (Find(u[0]) == x) ans[u[1]] = cuv;
            else qq[x].push_back(u);
        }
        qq[y].clear();
        p[y] = x;
        sz[x] += sz[y];
    };
    for (int i = 0; i < m; i++) {
        cuv = all[i][0];
        Unite(all[i][1], all[i][2]);
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << en;
    }
    return 0;
}

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