Submission #1204204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204204		Newtonabc	Evacuation plan (IZhO18_plan)	C++20	100 / 100	729 ms	72272 KiB

plan

#include<bits/stdc++.h>
#define pli pair<long long,int>
using namespace std;
const int N=1e5+10;
vector<pair<long long,int>> adj[N],t[N];
long long d[N];
int pa[N],dp[N][20],dep[N];
long long mn[N][20];
bool vs[N];
vector<pair<int,int>> etmp;
//edge list
vector<pair<int,pair<int,int>>> e;
priority_queue<pli,vector<pli>,greater<pli>> q;
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
void dfs(int u,int p){
    dp[u][0]=p;
    mn[u][0]=d[u];
    for(auto [w,v]:t[u]){
        if(v==p) continue;
        dep[v]=dep[u]+1;
        dfs(v,u);
    }
}
int lca(int u,int v){
    long long ret=LLONG_MAX;
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=19;i>=0;i--) if(dep[dp[v][i]]>=dep[u]) ret=min(ret,mn[v][i]),v=dp[v][i];
    //cout<<u <<" " <<v <<" ";
    if(u==v) return min(ret,d[u]);
    for(int i=19;i>=0;i--) if(dp[u][i]!=dp[v][i]) ret=min({ret,mn[u][i],mn[v][i]}),u=dp[u][i],v=dp[v][i];
    return min({ret,d[u],d[v],d[dp[u][0]]});
}
int main(){
    int n,m;
    cin>>n >>m;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u >>v >>w;
        etmp.push_back({u,v});
        adj[u].push_back({w,v});
        adj[v].push_back({w,u});
    }
    for(int i=1;i<=n;i++) pa[i]=i,d[i]=LLONG_MAX;
    int k;
    cin>>k;
    for(int i=1;i<=k;i++){
        int inp;
        cin>>inp;
        d[inp]=0;
        q.push({0,inp});
    }
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vs[u]) continue;
        vs[u]=true;
        for(auto [w,v]:adj[u]){
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                q.push({d[v],v});
            }
        }
    }
    // for(int i=1;i<=n;i++) cout<<d[i] <<" ";
    // cout<<"\n";
    for(auto [u,v]:etmp) e.push_back({min(d[u],d[v]),{u,v}});
    sort(e.begin(),e.end(),greater<pair<int,pair<int,int>>>());
    for(auto [w,p]:e){
        auto [u,v]=p;
        if(root(u)==root(v)) continue;
        pa[root(u)]=root(v);
        t[u].push_back({w,v});
        t[v].push_back({w,u});
    }
    dfs(1,1);
    // for(int i=1;i<=n;i++) cout<<dep[i] <<" ";
    // cout<<"\n";
    for(int i=1;i<20;i++) for(int j=1;j<=n;j++) dp[j][i]=dp[dp[j][i-1]][i-1],mn[j][i]=min(mn[j][i-1],mn[dp[j][i-1]][i-1]);
    int q;
    cin>>q;
    while(q--){
        int u,v;
        cin>>u >>v;
        cout<<lca(u,v) <<"\n";
    }
}

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