Submission #639498

#	Time	Username	Problem	Language	Result	Execution time	Memory
639498		classic	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1181 ms	32076 KiB

plan

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

struct DSU {
    int n;
    vector<int> p;

    DSU(int _n) : n(_n) {
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
    }

    int leader(int u) {
        return (p[u] == u ? u : p[u] = leader(p[u]));
    }

    void merge(int u, int v) {
        u = leader(u);
        v = leader(v);
        if (u == v) {
            return;
        }
        p[u] = v;
        return;
    }

    bool same(int u, int v) {
        return (leader(u) == leader(v));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    int k;
    cin >> k;
    vector<int> dist(n, 1e9);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    while (k--) {
        int u;
        cin >> u;
        u--;
        dist[u] = 0;
        pq.emplace(0, u);
    }
    while (!pq.empty()) {
        pair<int, int> top = pq.top();
        pq.pop();
        int u = top.second;
        int du = top.first;
        for (pair<int, int> e : adj[u]) {
            int v = e.first;
            int w = e.second;
            if (dist[v] > du + w) {
                dist[v] = du + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    vector<pair<int, int>> dist1;
    for (int i = 0; i < n; i++) {
        dist1.emplace_back(dist[i], i);
    }
    sort(dist1.begin(), dist1.end());
    int q;
    cin >> q;
    vector<pair<int, int>> queries(q);
    vector<int> low(q), hig(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].first >> queries[i].second;
        queries[i].first--;
        queries[i].second--;
        low[i] = 0;
        hig[i] = n - 1;
    }
    vector<pair<int, int>> events;
    while (true) {
        events.clear();
        for (int i = 0; i < q; i++) {
            if (low[i] < hig[i]) {
                events.emplace_back((low[i] + hig[i] + 1) >> 1, i);
            }
        }
        if (events.empty()) {
            break;
        }
        DSU d(n);
        sort(events.begin(), events.end());
        int ptr = events.size() - 1;
        for (int i = n - 1; i >= 0; i--) {
            int u = dist1[i].second;
            for (pair<int, int> v : adj[u]) {
                if (dist[v.first] >= dist[u]) {
                    d.merge(u, v.first);
                }
            }
            while (ptr >= 0 && events[ptr].first >= i) {
                int idx = events[ptr].second;
                if (d.same(queries[idx].first, queries[idx].second)) {
                    low[idx] = events[ptr].first;
                } else {
                    hig[idx] = events[ptr].first - 1;
                }
                ptr -= 1;
            }
        }
    }
    for (int i = 0; i < q; i++) {
        cout << dist1[low[i]].first << '\n';
    }
    return 0;
}

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