Submission #114588

#	Time	Username	Problem	Language	Result	Execution time	Memory
114588		mosquir	Evacuation plan (IZhO18_plan)	C++14	100 / 100	953 ms	60668 KiB

plan

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

const int N = 100100 , L = 17 ;
int n , m , k , Q;

int p[N][L] , dep[N];
ll mn[N][L];

ll dis[N];
int par[N];

vector<pair<int,int>>adj[N];
vector<int>ADJ[N];
vector< pair< ll , pair<int,int> > >edges;
priority_queue<pair<ll,int>>pq;

int get(int x){
if( x == par[x] )return x;
return par[x]=get(par[x]);
}

void mrg(int x,int y){
x=get(x); y=get(y);
if( x == y )return;
if( rand()&1 )swap(x,y);
par[x]=y;
}

void dij(){

    while( !pq.empty() ){
        ll d = -pq.top().first;
        int u = pq.top().second;

        pq.pop();
        if( d != dis[u] )continue;

        for(auto e:adj[u]){
            int v = e.first;
            int w = e.second;

            if( dis[v] > dis[u] + 1ll*w ){
                dis[v] = dis[u] + 1ll*w;
                pq.push( {-dis[v],v} );
            }
        }
    }
}

void dfs(int u,int dad){
dep[u]=1+dep[dad];
p[u][0]=dad;
mn[u][0]=dis[u];

for(int j=1;j<L;j++){
    p[u][j]=p[ p[u][j-1] ][j-1];
    mn[u][j]=min(mn[u][j-1],mn[p[u][j-1]][j-1]);
}

for(auto v:ADJ[u])
    if( v != dad )
        dfs(v,u);
}

int LCA(int u,int v){
if( u == v )return u;
if( dep[u] < dep[v] )swap(u,v);

int k = dep[u]-dep[v];

for(int i=0;i<L;i++)
    if( k & (1<<i) )
        u=p[u][i];

if( u == v )return u;

for(int i=L-1;i>=0;i--)
    if( p[u][i] != p[v][i] )
        u=p[u][i],v=p[v][i];

return p[u][0];
}

ll f(int u,int k){
ll ret=mn[u][0];
for(int i=0;i<L;i++)
    if( k&(1<<i) ){
        ret=min(ret,mn[u][i]);
        u=p[u][i];
    }
return ret;
}

void solve(){

cin>>n>>m;
edges.clear();
for(int i=1;i<=n;i++){
        dis[i]=1ll<<50;
        adj[i].clear();
        ADJ[i].clear();
        par[i]=i;
        for(int j=0;j<L;j++)
            mn[i][j]=1ll<<50,p[i][j]=0;

}
while( !pq.empty() )pq.pop();




while( m-- ){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    adj[u].push_back( {v,w} );
    adj[v].push_back( {u,w} );
}
cin>>k;
for(int i=0;i<k;i++){
    int x;
    scanf("%d",&x);
    dis[x]=0ll;
    pq.push({0,x});
}
dij();

for(int u=1;u<=n;u++)
    for(auto e:adj[u]){
        int v = e.first;
        ll w = min(dis[u],dis[v]);
        edges.push_back( { w , { u , v } } );
    }

sort(edges.begin(),edges.end());
reverse(edges.begin(),edges.end());

for(auto e:edges){
        int u = e.second.first;
        int v = e.second.second;
        if( get(u) == get(v) )continue;
        mrg(u,v);
        ADJ[u].push_back(v);
        ADJ[v].push_back(u);
}

dfs(1,0);
cin>>Q;
while( Q-- ){

    int u,v;
    scanf("%d %d",&u,&v);

    int k = LCA(u,v);
    ll ans = min( f(u,dep[u]-dep[k]+1) , f(v,dep[v]-dep[k]+1) );
    printf("%lld\n",ans);
}

}

int main(){

solve();
return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void solve()':
plan.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d",&u,&v,&w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
plan.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x);
     ~~~~~^~~~~~~~~
plan.cpp:153: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