Submission #40619

#	Time	Username	Problem	Language	Result	Execution time	Memory
40619		alenam0161	Evacuation plan (IZhO18_plan)	C++14	100 / 100	908 ms	49996 KiB

plan

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

const int N = 1e5+7;
vector<int> g[N],cost[N];
int di[N];
bool used[N];
int par[N];
int fpar(int v){
    return v==par[v] ?v:par[v]=fpar(par[v]);
}
int up[N][25],val[N][25];
int tin[N],tout[N],ti=0;
void dfs(int v,int p){
    tin[v]=++ti;
    up[v][0]=p;
    val[v][0]=min(di[v],di[p]);
    for(int i=1;i<=20;++i){up[v][i]=up[up[v][i-1]][i-1];val[v][i]=min(val[v][i-1],val[up[v][i-1]][i-1]);
    }
    for(int to:g[v]){
        if(to==p)continue;
        dfs(to,v);
    }
    tout[v]=++ti;
}
bool in(int v,int u){
    return tin[v]<=tin[u]&&tout[u]<=tout[v];
}
int get_ans(int u,int v){
    int ans=1e9;
    for(int i=20;i>=0;i--){
        if(in(u,up[v][i])==true){
            ans=min(ans,val[v][i]);
            v=up[v][i];
        }
    }
    return min(ans,di[u]);
}
int lca(int v,int u){
    if(in(v,u))return v;
    if(in(u,v))return u;
    for(int i=20;i>=0;i--)if(in(up[v][i],u)==false)v=up[v][i];
    return up[v][0];
}
int ans(int v,int u){
    int k=lca(u,v);
    return min(get_ans(k,v),get_ans(k,u));
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        g[u].push_back(v);
        g[v].push_back(u);
        cost[u].push_back(c);
        cost[v].push_back(c);
    }
    int k;
    scanf("%d",&k);
    memset(di,63,sizeof(di));
    priority_queue<pair<int,int>> q;
    for(int i=1;i<=k;++i){
        int l;
        scanf("%d",&l);
        di[l]=0;
        q.push({0,l});
    }
    for(int i=1;i<=n;++i){
        int v=-1;
        while(!q.empty()){
            v=q.top().second;q.pop();
            if(used[v]==false){
                break;
            }
        }
        if(v==-1||used[v])break;
        used[v]=true;
        for(int j=0;j<g[v].size();++j){
            int to=g[v][j];
            int c=cost[v][j];
            if(di[to]>di[v]+c){
                di[to]=di[v]+c;
                q.push({-di[to],to});
            }
        }
    }
    vector<pair<int,int>> ma;
    for(int i=1;i<=n;++i){
        ma.push_back({di[i],i});
        par[i]=i;
    }
    sort(ma.begin(),ma.end());
    vector<pair<int,int>> kox;
    srand(107);
    memset(used,0,sizeof(used));
    for(int i=ma.size()-1;i>=0;i--){
        int v=ma[i].second;
        used[v]=true;
        for(int to:g[v]){
            if(used[to]==false)continue;
            int x=fpar(v);
            int y=fpar(to);
            if(x!=y){
                kox.push_back({v,to});
                if(rand()&1){
                    par[x]=y;
                }
                else par[y]=x;
            }
        }
    }
    for(int i=0;i<=n;++i)g[i].clear();
    for(pair<int,int> to:kox){
        g[to.second].push_back(to.first);
        g[to.first].push_back(to.second);
    }
/*
    for(int i=1;i<=n;++i){
        cout<<di[i]<< " "<<i<<endl<<"kox:";
        for(int to:g[i]){
            cout<<to<<" ";
        }
        cout<<endl;
    }
*/
    dfs(1,1);
   int query;
   scanf("%d",&query);
   for(int i=0;i<query;++i){
    int u,v;
    scanf("%d%d",&u,&v);
    printf("%d\n",ans(u,v));
   }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'int main()':
plan.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<g[v].size();++j){
                     ~^~~~~~~~~~~~
plan.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&u,&v,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&k);
     ~~~~~^~~~~~~~~
plan.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&l);
         ~~~~~^~~~~~~~~
plan.cpp:130:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&query);
    ~~~~~^~~~~~~~~~~~~
plan.cpp:133:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&u,&v);
     ~~~~~^~~~~~~~~~~~~~

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