Submission #1011051

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011051		phoenix	Evacuation plan (IZhO18_plan)	C++17	100 / 100	382 ms	47308 KiB

plan

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;
const int N = 100100;

int n;
vector<pair<int, int>> g[N];
vector<int> npp;

vector<ll> Dijkstra() {
    vector<ll> dist(n + 1, INF);
    for (int c : npp) 
        dist[c] = 0;
    
    set<pair<ll, int>> st;
    for (int i = 1; i <= n; i++) {
        st.insert({dist[i], i});
    }
    while (!st.empty()) {
        int s = st.begin()->second;
        st.erase(st.begin());
        for (auto [to, w] : g[s]) {
            if (dist[to] > dist[s] + w) {
                st.erase({dist[to], to});
                dist[to] = dist[s] + w;
                st.insert({dist[to], to});
            }
        }
    }
    return dist;
}

vector<int> G[N];
int tin[N], tout[N], T;
int par[N][18];

void precalc(int s, int p) {
    tin[s] = T++;
    par[s][0] = p;
    for (int i = 1; i < 18; i++)
        par[s][i] = par[par[s][i - 1]][i - 1];
    for (int to : G[s]) if (to != p)
        precalc(to, s);
    tout[s] = T++;
}
bool up(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int lca(int u, int v) {
    if (up(u, v)) return u;
    if (up(v, u)) return v;
    for (int i = 17; i >= 0; i--) {
        if (!up(par[u][i], v))
            u = par[u][i];
    }
    return par[u][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int m, k;
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    cin >> k;
    for (int i = 0; i < k; i++) {
        int v;
        cin >> v;
        npp.push_back(v);
    }

    vector<ll> D = Dijkstra();
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int u, int v) {
        return D[u] > D[v];
    }); 

    vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) p[i] = i;
    function<int(int)> find = [&](int x) -> int {
        return p[x] = (p[x] == x ? x : find(p[x]));
    };

    bool us[n + 1] = {};
    for (int cur : ord) {
        us[cur] = true;
        for (auto [to, e] : g[cur]) {
            if (!us[to]) continue;
            to = find(to);
            if (to == cur) continue;
            G[cur].push_back(to);
            p[to] = cur;
        }
    }
    precalc(ord.back(), ord.back());
    int Q;
    cin >> Q;
    while (Q--) {
        int s, t;
        cin >> s >> t;
        cout << D[lca(s, t)] << '\n';
    }
}

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