Submission #332203

#	Time	Username	Problem	Language	Result	Execution time	Memory
332203		vitkishloh228	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1546 ms	70620 KiB

plan

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#define int long long
using namespace std;
int logn = 20;
vector<vector<int>> t;
vector<int> p, sz;
int getp(int v) {
    if (p[v] == v) return v;
    return p[v] = getp(p[v]);
}
void unite(int a, int b) {
    int a0 = a;
    a = getp(a);
    b = getp(b);
    if (a != b) {
        t[a].push_back(b);
        t[b].push_back(a);
        p[a] = b;
        //sz[a] += sz[b];
    }
}
vector<int> tin, tout;
int timer = 0;
vector<vector<int>> up;
void dfs(int v, int p = -1) {
    tin[v] = timer++;
    for (int i = 1; i < logn; ++i) {
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (auto u : t[v]) {
        if (u != p) {
            up[u][0] = v;
            dfs(u, v);
        }
    }
    tout[v] = timer;
}
bool par(int a, int b) {
    return (tin[a] <= tin[b] && tin[b] < tout[a]);
}
int lca(int a, int b) {
    if (par(a, b)) return a;
    if (par(b, a)) return b;
    for (int i = logn - 1; i >= 0; i--) {
        if (!par(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}
int32_t main() {
    int n, m;
    cin >> n >> m;
    vector < vector<pair<int, int>>> g(n);
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        g[a].push_back({ b,c });
        g[b].push_back({ a,c });
    }
    set<pair<int, int>> q;
    int k;
    cin >> k;
    vector<int> d(n, 1e17);
    while (k--) {
        int v;
        cin >> v;
        --v;
        d[v] = 0;
        q.insert({ 0,v });
    }
    while (q.size()) {
        int v = q.begin()->second;
        q.erase(q.begin());
        for (auto u : g[v]) {
           // cout << "fuck\n";
            
            if (d[u.first] > d[v] + u.second) {
                q.erase({ d[u.first],u.first });
                d[u.first] = d[v] + u.second;
                q.insert({ d[u.first],u.first });
            }
        }
    }
    //for (auto elem : d) cout << elem << ' ';
    //cout << endl;
    vector<pair<int, int>> arr(n);
    for (int i = 0; i < n; ++i) {
        arr[i] = { d[i],i };
    }
    sort(arr.begin(), arr.end());
    reverse(arr.begin(), arr.end());
    p = vector<int>(n);
    sz = vector<int>(n, 1);
    for (int i = 0; i < n; ++i) {
        p[i] = i;
    }
    tin.resize(n);
    tout.resize(n);
    up = vector<vector<int>>(n, vector<int>(logn, arr.back().second));
    t.resize(n);
    for (auto elem : arr) {
        for (auto u : g[elem.second]) {
            if (d[elem.second] <= d[u.first])
            unite(u.first, elem.second);
        }
    }
    dfs(arr.back().second);
    int Q;
    cin >> Q;
    while (Q--) {
        int s, t;
        cin >> s >> t;
        --s, --t;
        int v = lca(s, t);
        cout << d[v] << '\n';   
    }
}

Compilation message (stderr)

plan.cpp: In function 'void unite(long long int, long long int)':
plan.cpp:15:9: warning: unused variable 'a0' [-Wunused-variable]
   15 |     int a0 = a;
      |         ^~

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