Submission #440102

#	Time	Username	Problem	Language	Result	Execution time	Memory
440102		JovanB	Evacuation plan (IZhO18_plan)	C++17	100 / 100	882 ms	54560 KiB

plan

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

using ll = long long;
using ld = long double;

const int MAXN = 100000;
const int INF = 1000000000;
const int MXLOG = 18;

struct Edge{
    int a, b, c;
    bool operator <(const Edge &x){
        return c > x.c;
    }
};

vector <Edge> edges;

int dist[MAXN+5];
vector <pair <int, int>> graf[MAXN+5];

struct DSU{
    int n;
    int par[MAXN+5];
    int sz[MAXN+5];
    void init(int g){
        n = g;
        for(int i=1; i<=n; i++) par[i] = i;
        for(int i=1; i<=n; i++) sz[i] = 1;
    }
    int root(int x){
        if(par[x] == x) return x;
        return par[x] = root(par[x]);
    }
};

vector <pair <int, int>> drvo[MAXN+5];

int in[MAXN+5];
int out[MAXN+5];
int mnd[MAXN+5][MXLOG+1];
int par[MAXN+5][MXLOG+1];

int tjm;

void dfs(int v, int p, int gr){
    in[v] = ++tjm;
    par[v][0] = p;
    mnd[v][0] = gr;
    for(int j=1; j<=MXLOG; j++){
        par[v][j] = par[par[v][j-1]][j-1];
        mnd[v][j] = min(mnd[v][j-1], mnd[par[v][j-1]][j-1]);
    }
    for(auto c : drvo[v]) if(c.first != p) dfs(c.first, v, c.second);
    out[v] = tjm;
}

bool is_parent(int a, int b){
    return (a == 0) || (in[a] <= in[b] && out[b] <= out[a]);
}

int lca(int a, int b){
    if(is_parent(a, b)) return a;
    for(int j=MXLOG; j>=0; j--) if(!is_parent(par[a][j], b)) a = par[a][j];
    return par[a][0];
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        graf[a].push_back({b, c});
        graf[b].push_back({a, c});
        edges.push_back({a, b, c});
    }
    for(int i=1; i<=n; i++) dist[i] = INF;
    int plants;
    cin >> plants;
    set <pair <int, int>> q;
    while(plants--){
        int v;
        cin >> v;
        dist[v] = 0;
        q.insert({0, v});
    }
    while(!q.empty()){
        int v = q.begin()->second;
        q.erase(q.begin());
        for(auto c : graf[v]){
            if(dist[c.first] > dist[v] + c.second){
                q.erase({dist[c.first], c.first});
                dist[c.first] = dist[v] + c.second;
                q.insert({dist[c.first], c.first});
            }
        }
    }
    for(int i=0; i<m; i++){
        Edge c = edges[i];
        edges[i].c = min(dist[c.a], dist[c.b]);
    }
    sort(edges.begin(), edges.end());
    DSU dsu;
    dsu.init(n);
    for(auto edge : edges){
        int a = edge.a;
        int b = edge.b;
        int c = edge.c;
        int a1 = dsu.root(a);
        int b1 = dsu.root(b);
        if(a1 == b1) continue;
        if(dsu.sz[a1] < dsu.sz[b1]) swap(a1, b1);
        dsu.sz[a1] += dsu.sz[b1];
        dsu.par[b1] = a1;
        drvo[a].push_back({b, c});
        drvo[b].push_back({a, c});
    }
    dfs(1, 0, 0);
    int cases;
    cin >> cases;
    while(cases--){
        int a, b;
        cin >> a >> b;
        int x = lca(a, b);
        int res = dist[x];
        for(int j=MXLOG; j>=0; j--){
            if(!is_parent(par[a][j], x)){
                res = min(res, mnd[a][j]);
                a = par[a][j];
            }
        }
        if(a != x) res = min(res, mnd[a][0]);
        for(int j=MXLOG; j>=0; j--){
            if(!is_parent(par[b][j], x)){
                res = min(res, mnd[b][j]);
                b = par[b][j];
            }
        }
        if(b != x) res = min(res, mnd[b][0]);
        cout << res << "\n";
    }
    return 0;
}

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