Submission #1021338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021338		aufan	Evacuation plan (IZhO18_plan)	C++17	100 / 100	1124 ms	63168 KiB

plan

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int inff = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, m;
        cin >> n >> m;

        vector<vector<pair<int, int>>> v(n + 1);
        for (int i = 0; i < m; i++) {
                int a, b, c;
                cin >> a >> b >> c;

                v[a].push_back({b, c});
                v[b].push_back({a, c});
        }

        int k;
        cin >> k;

        vector<int> dist(n + 1, inff);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int i = 0; i < k; i++) {
                int x;
                cin >> x;

                dist[x] = 0;
                pq.push({dist[x], x});
        }

        while (!pq.empty()) {
                auto [w, x] = pq.top();
                pq.pop();

                if (w > dist[x]) continue;

                for (auto [z, c] : v[x]) {
                        if (w + c < dist[z]) {
                                dist[z] = w + c;
                                pq.push({dist[z], z});
                        }
                }
        }

        vector<int> ord(n);
        iota(ord.begin(), ord.end(), 1);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
                return dist[x] > dist[y];
        });

        int q;
        cin >> q;

        vector<vector<array<int, 5>>> qr(n);
        for (int i = 0; i < q; i++) {
                int a, b;
                cin >> a >> b;

                int lo = 0, hi = n - 1;
                qr[(lo + hi) / 2].push_back({lo, hi, a, b, i});
        }

        vector<int> ans(q);
        for (int _ = 0; _ < 20; _++) {
                vector<int> par(n + 1), sz(n + 1, 1);
                iota(par.begin(), par.end(), 0);

                function<int(int)> root = [&](int x) {
                        return par[x] == x ? x : par[x] = root(par[x]);
                };

                auto join = [&](int x, int y) {
                        x = root(x); y = root(y);
                        if (x == y) return;
                        if (sz[x] < sz[y]) swap(x, y);
                        sz[x] += sz[y];
                        par[y] = x;
                };

                auto check = [&](int x, int y) {
                        return root(x) == root(y);
                };

                vector<vector<array<int, 5>>> tmp(n);
                for (int i = 0; i < n; i++) {
                        int x = ord[i];

                        for (auto [z, c] : v[x]) {
                                if (dist[z] >= dist[x]) {
                                        join(x, z);
                                }
                        }

                        for (auto &[lo, hi, a, b, j] : qr[i]) {
                                if (check(a, b)) {
                                        ans[j] = dist[x];
                                        hi = i - 1;
                                } else {
                                        lo = i + 1;
                                }

                                if (lo <= hi) tmp[(lo + hi) / 2].push_back({lo, hi, a, b, j});
                        }
                }
                
                swap(qr, tmp);
        }

        for (int i = 0; i < q; i++) cout << ans[i] << '\n';
        
        return 0;
}

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