Submission #503615

#	Time	Username	Problem	Language	Result	Execution time	Memory
503615		Ronin13	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1424 ms	80516 KiB

plan

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define inf 1e9+1
#define linf 1e18+1
using namespace std;
const int NMAX=1e5+1;
vector<vector<pair<int,ll> > >g(NMAX);
vector<vector<int> >g1(NMAX);
vector<int>p(NMAX);
vector<ll>d(NMAX);
vector<vector<int> >G(NMAX);
vector<int>sz(NMAX);

void make_set(int v){
    p[v]=v;
    sz[v]=1;
    return;
}
int find_set(int v){
    return p[v]==v?v:p[v]=find_set(p[v]);
}
void union_sets(int a,int b){
    a=find_set(a);
    b=find_set(b);
    if(a!=b){
        if(sz[a]<sz[b])swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
    }
}

int a[NMAX][20];
ll mn[NMAX][20];
int t_in[NMAX],t_out[NMAX];
int d1[NMAX];
int timer=0;

void dfs(int v,int e=-1){
    t_in[v]=timer++;
    a[v][0]=e;
    if(e!=-1)mn[v][0]=d[e];
    for(int to:G[v]){
        if(to==e)continue;
        d1[to]=d1[v]+1;
        dfs(to,v);
    }
    t_out[v]=timer++;
}

bool is_ancestor(int u,int v){
    return t_in[v]>t_in[u]&&t_out[v]<t_out[u];
}
int n;
int root;
void prep(){
    for(int i=1;i<=n;i++){
        for(int j=0;j<20;j++)a[i][j]=-1,mn[i][j]=linf;
    }
    dfs(root);
    for(int j=1;j<20;j++){
        for(int i=1;i<=n;i++){
            if(a[i][j-1]!=-1)a[i][j]=a[a[i][j-1]][j-1],mn[i][j]=min(mn[a[i][j-1]][j-1],mn[i][j-1]);
        }
    }
}

int lca(int u,int v){
    if(is_ancestor(u,v))return u;
    if(is_ancestor(v,u))return v;
    for(int j=19;j>=0;j--){
        int x=a[u][j];
        if(x!=-1&&!is_ancestor(x,v))u=x;
    }
    return a[u][0];
}

ll binlift(int u,int dist){
    ll ans=d[u];
    while(dist){
        int t=log2(dist);
        ans=min(ans,mn[u][t]);
        u=a[u][t];
        dist-=(1<<t);
    }
    return ans;
}

bool comp(int a,int b){
    return d[a]>d[b];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)d[i]=linf;
    int m;cin>>m;
    for(int i=1;i<=m;i++){
        int u,v;ll len;cin>>u>>v>>len;
        g[u].epb(v,len);
        g[v].epb(u,len);
        g1[u].pb(v);
        g1[v].pb(u);
    }
    int k;cin>>k;
    set<pair<ll,int> >q;
    for(int i=1;i<=k;i++){
        int x;cin>>x;
        d[x]=0;
        q.insert({d[x],x});
    }
    while(!q.empty()){
        int v=q.begin()->s;
        q.erase(q.begin());
        for(pair<int,ll> x:g[v]){
            int to=x.f;
            ll len=x.s;
            if(d[to]>d[v]+len){
                q.erase({d[to],to});
                d[to]=d[v]+len;
                q.insert({d[to],to});
            }
        }
    }
    vector<int>vec;
    for(int i=1;i<=n;i++)vec.pb(i),make_set(i);
    int used[n+1];
    for(int i=1;i<=n;i++)used[i]=0;
    sort(vec.begin(),vec.end(),comp);
    for(int x:vec){
        sort(g1[x].begin(),g1[x].end(),comp);
        used[x]=1;
        for(int to:g1[x]){
            if(!used[to])continue;
            if(find_set(to)!=find_set(x))union_sets(to,x),G[x].pb(to),G[to].pb(x);
        }
    }
    root=vec[0];
    prep();
    int ask;cin>>ask;
    while(ask--){
        int u,v;cin>>u>>v;
        int an=lca(u,v);
        cout<<min(binlift(u,d1[u]-d1[an]),binlift(v,d1[v]-d1[an]))<<"\n";
    }
    return 0;
}

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