Submission #547030

#	Time	Username	Problem	Language	Result	Execution time	Memory
547030		Jomnoi	Evacuation plan (IZhO18_plan)	C++17	100 / 100	676 ms	59392 KiB

plan

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

const int MAX_N = 1e5 + 10;
const int MAX_M = 5e5 + 10;
const int INF = 1e9 + 7;

int A[MAX_M], B[MAX_M];
vector <pair <int, int>> adj[MAX_N];
int dist[MAX_N];
bool visited[MAX_N];
int parent[MAX_N];
set <int> path[MAX_N];
int ans[MAX_N];

int root(const int &u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int c;
        cin >> A[i] >> B[i] >> c;
        adj[A[i]].emplace_back(B[i], c);
        adj[B[i]].emplace_back(A[i], c);
    }

    int k;
    cin >> k;
    priority_queue <pair <int, int>> pq;
    fill(dist, dist + n + 1, INF);
    while(k--) {
        int g;
        cin >> g;
        dist[g] = 0;
        pq.emplace(0, g);
    }

    while(!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if(visited[u] == true) {
            continue;
        }
        visited[u] = true;
        for(auto [v, w] : adj[u]) {
            if(visited[v] == true or dist[u] + w >= dist[v]) {
                continue;
            }

            dist[v] = dist[u] + w;
            pq.emplace(-dist[v], v);
        }
    }

    int q;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        int s, t;
        cin >> s >> t;
        path[s].insert(i);
        path[t].insert(i);
    }

    vector <tuple <int, int, int>> edge;
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for(int i = 1; i <= m; i++) {
        edge.emplace_back(min(dist[A[i]], dist[B[i]]), A[i], B[i]);
    }

    sort(edge.rbegin(), edge.rend());
    for(auto [w, a, b] : edge) {
        int u = root(a), v = root(b);
        if(u == v) {
            continue;
        }

        if(path[u].size() < path[v].size()) {
            swap(u, v);
        }
        for(auto i : path[v]) {
            if(path[u].count(i)) {
                ans[i] = w;
                path[u].erase(i);
            }
            else {
                path[u].insert(i);
            }
        }
        parent[v] = u;
    }

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