Submission #467838

#	Time	Username	Problem	Language	Result	Execution time	Memory
467838		nickmet2004	Evacuation plan (IZhO18_plan)	C++11	0 / 100	232 ms	41028 KiB

plan

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair<int , int> ipair;
const int N = 5e5 + 5;
struct TEdges{
    int u , v , w;
    bool operator<(const TEdges &X) const{
        return w > X.w;
    }
};
int n , m , k , q;
vector<ipair> adj[N];
TEdges E[N];
priority_queue<ipair , vector<ipair> , greater<ipair>> pq;
int d[N] , P[N][20] , depth[N] , mn[N][20] , sz[N] , p[N];
int Find(int x){
    return (x == p[x]) ? x : p[x] = Find(p[x]);
}
int Union(int u , int v){
    int U = Find(u) ,V = Find(v);
    if(U == V) return 0;
    if(sz[U] < sz[V]) swap(U , V);
    sz[U] += sz[V]; p[V] = U;
    return 1;
}
void dfs(int u, int p ){
    P[u][0]= p;
    for(int i = 1; i <= 17; ++i) {P[u][i] = P[P[u][u - 1]][i - 1] ; mn[u][i] = min(mn[u][i - 1] , mn[P[u][i - 1]][i - 1]); }
    for(auto X : adj[u]){
        int v = X.f , w = X.s;
        if(v == p) continue;
        mn[v][0] = w;
        depth[v] = depth[u] + 1;
        dfs(v ,u);
    }
}
int LCA(int u, int v){
    int res = 2e9;
    if(depth[u] < depth[v]) swap(u , v);
    int k = depth[u] - depth[v];
    for(int i = 17; ~i; --i){
        if(k>>i&1){ res = min(res , mn[u][i]) ; u= P[u][i];
        }
    }
    if(u == v) return res;
    for(int i = 17; ~i; --i){
        if(P[u][i] != P[v][i]){
            res = min({res , mn[u][i] , mn[v][i]}); u = P[u][i] ; v = P[v][i];
        }
    }
    return min({res , mn[u][0] , mn[v][0]});
}
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; ++i){
        int u , v , w; cin >> u >> v >> w;
        adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
        E[i].u = u; E[i].v = v; E[i].w = w;
    }
    cin >> k;
    for(int i = 1; i <= n; ++i) d[i] = 2e9;
    for(int i= 0;i < k; ++i){
        int u; cin >> u;
        d[u] = 0; pq.push({0 , u});
    }
    while(!pq.empty()){
        auto X = pq.top(); pq.pop();
        if(X.f != d[X.s]) continue;
        for(ipair N : adj[X.s]){
            if(d[N.f] > X.f + N.s){
                d[N.f] = X.f + N.s;
                pq.push({d[N.f], N.f});
            }
        }
    }
    for(int i = 0; i < n; ++i) for(int j = 0; j < 20; ++j) mn[i][j] = 2e9;
    for(int i = 1; i <= n; ++i) p[i] = i , sz[i] = 1;
    for(int i = 0; i < m; ++i) E[i].w = min(d[E[i].u] , d[E[i].v]);
    for(int i = 1; i <= n; ++i) adj[i].clear();
    sort(E , E + m);
    for(int i = 0; i < m; ++i){
        int u = E[i].u , v = E[i].v ,w = E[i].w;
        if(Union(u , v)){
            adj[u].emplace_back(v , w); adj[v].emplace_back(u , w);
        }
    }
    dfs(1 ,0);

    cin >> q;
    while(q--){
        int u , v;
        cin >> u >> v;
        cout << LCA(u ,v) << endl;
    }
return 0;
}

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