제출 #608776

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608776		pakhomovee	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2362 ms	33004 KiB

plan

#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <set>
#include <numeric>

using namespace std;

const int inf = 2e9;
const int maxn = 1e5;

int p[maxn];

void init() { iota(p, p + maxn, 0); }
int c(int v) { return p[v] == v ? v : p[v] = c(p[v]); }
void unite(int u, int v) { p[c(u)] = c(v); }
bool united(int u, int v) { return c(u) == c(v); }

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    int k;
    cin >> k;
    vector<int> npp(k);
    for (int& i : npp) {
        cin >> i;
        --i;
    }
    set<pair<int, int>> s;
    vector<int> dist(n, inf);
    for (int i : npp) {
        dist[i] = 0;
        s.insert({ 0, i });
    }
    while (!s.empty()) {
        int v = s.begin()->second;
        s.erase(s.begin());
        for (auto [u, w] : g[v]) {
            if (dist[u] > dist[v] + w) {
                s.erase({ dist[u], u });
                dist[u] = dist[v] + w;
                s.insert({ dist[u], u });
            }
        }
    }
    vector<pair<int, int>> vs;
    for (int i = 0; i < n; ++i) {
        vs.push_back({ dist[i], i });
    }
    sort(vs.rbegin(), vs.rend());
    int q;
    cin >> q;
    vector<pair<int, int>> queries;
    for (int i = 0; i < q; ++i) {
        int s, t;
        cin >> s >> t;
        --s; --t;
        queries.push_back({ s, t });
    }
    vector<pair<int, int>> bs(q, make_pair(0, inf));
    for (int step = 0; step < 32; ++step) {
        init();
        vector<int> mid(q);
        for (int i = 0; i < q; ++i) {
            mid[i] = (bs[i].first + bs[i].second) / 2;
        }
        vector<bool> ok(q, false);
        vector<pair<int, int>> ord;
        for (int i = 0; i < q; ++i) {
            ord.push_back({ mid[i], i });
        }
        sort(ord.rbegin(), ord.rend());
        int ptr = 0;
        vector<bool> active(n, false);
        for (auto [d, v] : vs) {
            while (ptr < q && d < ord[ptr].first) {
                int i = ord[ptr++].second;
                ok[i] = united(queries[i].first, queries[i].second);
            }
            active[v] = true;
            for (auto [u, w] : g[v]) {
                if (active[u]) {
                    unite(u, v);
                }
            }
        }
        for (int i = 0; i < q; ++i) {
            if (!ok[i]) {
                bs[i].second = mid[i];
            } else {
                bs[i].first = mid[i];
            }
        }
    }
    for (int i = 0; i < q; ++i) {
        cout << bs[i].first << '\n';
    }
}

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