제출 #578067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578067		georgievskiy	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1024 ms	59116 KiB

plan

#include <iostream>
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int N = 1.01e5;
//const int N = 20;
vector<pii> g[N];
pii d[N];

int p[N], r[N], ans[N], used[N];
set<int> s[N];

int getP(int v) {
    while (p[v] != v)
        v = p[v];
    return v;
}

void unite(int x, int y, int cur) {
    x = getP(x), y = getP(y);
    if (x == y)
        return;
    if (r[y] > r[x])
        swap(x, y);
    if (r[y] == r[x])
        r[x]++;
    p[y] = x;

    for (int t : s[y]) {
        if (s[x].count(t)) {
            ans[t] = cur;
            s[x].erase(t);
        } else {
            s[x].insert(t);
        }
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--, b--;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    fill(d, d + n, make_pair(-1, 0));
    int k;
    cin >> k;
    priority_queue<pii> q;
    for (int i = 0; i < k; i++) {
        int r;
        cin >> r;
        r--;
        q.push({0, r});
        d[r].first = 0;
    }

    while (q.size()) {
        int dst = -q.top().first, v = q.top().second;
        q.pop();
        if (d[v].first > 0)
            continue;
        d[v].first = dst;
        for (auto u : g[v]) {
            if (d[u.first].first == -1) {
                q.push({- dst - u.second, u.first});
            }
        }
    }
    for (int i = 0; i < n; i++)
        d[i].second = i;
    sort(d, d + n);
    reverse(d, d + n);

    int qn;
    cin >> qn;
    for (int i = 0; i < qn; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        s[u].insert(i);
        s[v].insert(i);
    }
    iota(p, p + n, 0);

    for (int i = 0; i < n; i++) {
        int cur = d[i].first, v = d[i].second;
        used[v] = 1;
        int x = getP(v);
        for (auto u : g[v]) {
            if (used[u.first])
                unite(x, u.first, cur);
        }
    }

    for (int i = 0; i < qn; 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