Submission #1090980

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090980		Prophet_Sid	Evacuation plan (IZhO18_plan)	C++17	22 / 100	150 ms	58884 KiB

plan

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pii pair<int,int>
#define tpi tuple<int,int,int>
#define siz(x) (int)(x.size())
#define deb(x) cerr << "[" << #x << ": " << x << "]"

using namespace std;
using namespace __gnu_pbds;

template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mxN = 1e5+2;
const int inf = 1e9;
const int LG = 20;
vector<pii> g[mxN];
vector<int> adj[mxN<<1];
int dist[mxN], pa[mxN<<1], dan[mxN<<1];
bool vis[mxN];
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<tpi> edge;
int tin[mxN], tout[mxN], id = 0;
int bl[mxN][20];

int fp(int x){
    if(pa[x]==x) return x;
    return pa[x]=fp(pa[x]);
}

void dfs(int u, int p){
    tin[u]=++id;
    bl[u][0]=p;
    for(int i=1;i<LG;i++) bl[u][i]=bl[bl[u][i-1]][i-1];
    for(auto &v:adj[u]){
        if(v==p) continue;
        dfs(v, u);
    }
    tout[u]=id;
}

bool check(int u, int v){
    return tin[u]<=tin[v] && tout[u]>=tout[v];
}

int lca(int u, int v){
    if(check(u, v)) return u;
    if(check(v, u)) return v;
    for(int i=LG-1;i>=0;--i) if(!check(bl[u][i], v)) u = bl[u][i];
    return bl[u][0];
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    for(int i=0;i<m;i++){
        int u,v,w; cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        edge.emplace_back(w, u, v);
    }
    int k; cin >> k;
    vector<int> a(k);
    for(auto &e:a) cin >> e;
    fill(dist+1, dist+1+n, inf);
    for(auto &e:a) pq.emplace(dist[e]=0, e);
    while(!pq.empty()){
        auto [d, u] = pq.top();
        pq.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto &[v, w]:g[u]){
            if(!vis[v] && dist[v]>d+w){
                dist[v]=d+w;
                pq.emplace(dist[v], v);
            }
        }
    }
    for(auto &[w, u, v]:edge) w = min(dist[u], dist[v]);
    sort(edge.begin(), edge.end());
    reverse(edge.begin(), edge.end());
    iota(pa+1, pa+2*n+1, 1);
    int c=n;
    for(auto &[w, u, v]:edge){
        int pu = fp(u), pv = fp(v);
        if(pu==pv) continue;
        pa[pv]=pu;
        ++c;
        dan[c]=w;
        pa[pu]=pa[pv]=c;
        adj[c].push_back(pu);
        adj[c].push_back(pv);
    }
    dfs(c, c);
    int q; cin >> q;
    while(q--){
        int s,t; cin >> s >> t;
        cout << dan[lca(s, t)] << "\n";
    }

    return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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