Submission #1219407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219407		trufanov.p	Evacuation plan (IZhO18_plan)	C++20	100 / 100	361 ms	56308 KiB

plan

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_map>
#include <map>
#include <numeric>
#include <set>
#include <queue>
#include <random>
#include <unordered_set>

using namespace std;

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;

const int INF = 1e9 + 7;

class CustomDSU {
private:
    int n;
    vector<int> p;
    vector<int> d;
    vector<unordered_set<int>> qr;
    int get_par(int v) {
        if (v == p[v]) {
            return v;
        }
        return p[v] = get_par(p[v]);
    }
public:
    CustomDSU(int n_) :n(n_) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        d.resize(n);
        qr.resize(n);
    }
    void addQuery(int u, int v, int ind) {
        qr[u].insert(ind);
        qr[v].insert(ind);
    }
    void unite(int u, int v, int w, vector<int>& ans) {
        u = get_par(u);
        v = get_par(v);
        if (u != v) {
            if (d[u] > d[v]) {
                swap(u, v);
            }
            p[u] = v;
            if (d[u] == d[v]) {
                d[v]++;
            }
            if (qr[u].size() > qr[v].size()) {
                swap(qr[u], qr[v]);
            }
            for (int x : qr[u]) {
                if (qr[v].count(x)) {
                    ans[x] = w;
                    qr[v].erase(x);
                } else {
                    qr[v].insert(x);
                }
            }
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> gr(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        gr[u].push_back({ v, w });
        gr[v].push_back({ u, w });
    }
    vector<int> d(n, INF);
    set<pair<int, int>> s;
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
        int v;
        cin >> v;
        v--;
        d[v] = 0;
        s.insert({ d[v], v });
    }
    while (!s.empty()) {
        int v = s.begin()->second;
        s.erase(s.begin());
        for (auto& [u, w] : gr[v]) {
            if (d[u] > d[v] + w) {
                s.erase({ d[u], u });
                d[u] = d[v] + w;
                s.insert({ d[u], u });
            }
        }
    }
    CustomDSU dsu(n);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        dsu.addQuery(u, v, i);
    }
    vector<int> vert(n);
    iota(vert.begin(), vert.end(), 0);
    sort(vert.begin(), vert.end(), [&](const int& a, const int& b) -> bool {
        return d[a] > d[b];
    });
    vector<int> ans(q, -1);
    for (int v : vert) {
        for (auto& [u, _] : gr[v]) {
            if (d[u] >= d[v]) {
                dsu.unite(v, u, d[v], ans);
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }
}

/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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