Submission #861557

#	Time	Username	Problem	Language	Result	Execution time	Memory
861557		PagodePaiva	Evacuation plan (IZhO18_plan)	C++17	100 / 100	901 ms	107284 KiB

plan

#include<bits/stdc++.h>
#define N 100010
#define inf 1e18
#define int long long
#define LOGN 21
#define fr first
#define sc second

using namespace std;

int n, m;
vector <pair <int, int>> g[N];
int dist[N];
vector <pair <int, int>> arestas;
vector <array <int, 3>> novas_arestas;
vector <array <int, 3>> arvore;
vector <pair <int, int>> gc[N];

struct DSU{
    int pai[N], sz[N];

    void init(){
        for(int i = 1;i <= n;i++){
            pai[i] = i;
            sz[i] = 1;
        }
        return;
    }

    int find(int x){
        return pai[x] = (x == pai[x] ? x : find(pai[x]));
    }

    void join(int a, int b){
        a = find(a);
        b = find(b);

        if(a == b) return;
        if(sz[a] > sz[b]) swap(a, b);

        sz[b] += sz[a];
        pai[a] = b;
        return;
    }

    bool get(int a, int b){
        if(find(a) == find(b)) return false;
        return true;
    }
} dsu;

int pai[N][LOGN];
int val[N][LOGN];
int alt[N];

void dfs(int v, int p){
    for(auto x : gc[v]){
        if(x.fr == p) continue;
        alt[x.fr] = alt[v] + 1;
        pai[x.fr][0] = v;
        val[x.fr][0] = x.sc;
        dfs(x.fr, v);
    }

    return;
}

int lca(int a, int b){
    if(alt[a] > alt[b]) swap(a, b);

    int t = alt[b] - alt[a];

    int res = inf;
    
    for(int i = LOGN-1;i >= 0;i--){
        if(((1 << i) & t) == 0) continue;
        res = min(res, val[b][i]);
        b = pai[b][i];
    } 


    for(int i = LOGN-1;i >= 0;i--){
        if(pai[a][i] == pai[b][i]) continue;
        res = min({res, val[a][i], val[b][i]});
        a = pai[a][i];
        b = pai[b][i];
    }

    return (a != b ? min(res, min(val[a][0], val[b][0])) : res);
}

int32_t main(){
    cin >> n >> m;

    for(int i = 1;i <= m;i++){
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
        arestas.push_back({a, b});
    }

    int k;
    cin >> k;

    vector <int> pesados;

    for(int i = 0;i < k;i++){
        int x;
        cin >> x;
        pesados.push_back(x);
    }

    for(int i = 1;i <= n;i++){
        dist[i] = inf;
    }

    priority_queue <pair <int, int>> pq;

    for(auto x : pesados){
        dist[x] = 0;
        pq.push({0, x});
    }

    while(!pq.empty()){
        auto [p, v] = pq.top();
        pq.pop();

        for(auto t : g[v]){
            auto [x, pes] = t;

            if(dist[x] > dist[v] + pes){
                dist[x] = dist[v] + pes;
                pq.push({-dist[x], x});
            }
        }
    }

    for(auto x : arestas){
        auto [a, b] = x;

        novas_arestas.push_back({min(dist[a], dist[b]), a, b});
    }

    sort(novas_arestas.begin(), novas_arestas.end());
    reverse(novas_arestas.begin(), novas_arestas.end());

    dsu.init();

    for(auto x : novas_arestas){
        auto [p, a, b] = x;

        if(dsu.get(a, b)){
            arvore.push_back({p, a, b});
            dsu.join(a, b);
        }
    }

    for(auto x : arvore){
        auto [p, a, b] = x;
        gc[a].push_back({b, p});
        gc[b].push_back({a, p});
    }

    // for(int i = 1;i <= n;i++){
    //     for(auto x : gc[i]){
    //         cout << i << ' ' << x.fr << ' ' << x.sc << '\n';
    //     }
    // }

    pai[1][0] = 1;
    val[1][0] = inf;

    dfs(1, 1);

    // for(int i = 1;i <= n)

    for(int i = 1;i <= LOGN-1;i++){
        for(int v = 1;v <= n;v++){
            pai[v][i] = pai[pai[v][i-1]][i-1];
            val[v][i] = min(val[v][i-1], val[pai[v][i-1]][i-1]);
        }
    }

    int q;
    cin >> q;

    while(q--){
        int a, b;
        cin >> a >> b;
        // cout << lca(a, b) << ' ';
        // cout << dist[a] << ' ' << dist[b] << '\n';

        cout << lca(a, b) << '\n';
    }

    return 0;
}

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