제출 #878771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878771		The_Samurai	Evacuation plan (IZhO18_plan)	C++17	0 / 100	1204 ms	524288 KiB

plan

#include <random>

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int inf = 1e9;

void solve() {
    int n, m, q;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    vector<pair<int, int>> danger(n + 1);
    for (int i = 1; i <= n; i++) danger[i] = make_pair(inf, i);
    {
        int k;
        cin >> k;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < k; i++) {
            int root;
            cin >> root;
            pq.emplace(0, root);
            danger[root].first = 0;
        }
        vector<bool> vis(n + 1);
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            d = -d;
            if (vis[u]) continue;
            vis[u] = true;
            for (auto [v, w]: g[u]) {
                if (danger[v].first <= d + w) continue;
                danger[v].first = d + w;
                pq.emplace(-danger[v].first, v);
            }
        }
        sort(danger.begin() + 1, danger.end());
    }
    cin >> q;
    vector<int> ans(q), copy(n + 1);
    vector<vector<pair<int, int>>> queries(n + 1);
    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;
        queries[s].emplace_back(t, i);
        queries[t].emplace_back(s, i);
    }

    int now;
    vector<int> p(n + 1), size(n + 1);
    vector<vector<int>> v(n + 1);
    for (int i = 1; i <= n; i++) {
        copy[danger[i].second] = danger[i].first;
        p[i] = i;
        size[i] = queries[i].size();
        v[i] = {i};
    }

    auto get = [&](auto &get, int a) -> int {
        return p[a] == a ? a : p[a] = get(get, p[a]);
    };
    auto add = [&](int a, int b) -> void {
        a = get(get, a); b = get(get, b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        p[a] = b;
        for (int s: v[a]) {
            vector<pair<int, int>> nw;
            for (auto [t, i]: queries[s]) {
                if (get(get, t) == b) ans[i] = now;
                else nw.emplace_back(t, i);
            }
            queries[s] = nw;
            size[b] += nw.size();
        }
        for (int s: v[a]) v[b].emplace_back(s);
        v[a].clear();
    };
    for (int i = n; i > 0; i--) {
        now = danger[i].first;
        int u = danger[i].second;
        for (auto [v, w]: g[u]) {
            if (copy[v] < now) continue;
            add(u, v);
        }
    }
    for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

int main() {
    srand(time(0));
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int queries = 1;
//    cin >> queries;

    for (int test_case = 1; test_case <= queries; test_case++) {
#ifdef sunnatov
        cout << "Test case: " << test_case << endl;
#endif
        solve();
        cout << '\n';
    }
}

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