Submission #42812

#	Time	Username	Problem	Language	Result	Execution time	Memory
42812		igzi	Evacuation plan (IZhO18_plan)	C++14	100 / 100	600 ms	27976 KiB

plan

#include <bits/stdc++.h>
#define maxN 100005
#define maxM 500005

using namespace std;
struct edge{
int u,v,w;};
edge e[maxM];
int i,x,y,z,q,m,n,k,dg[maxN],r[maxN];
pair <int,int> par[maxN];
vector < pair<int,int> > adj[maxN];
vector <int> ans,p;

int findr(int a,int v){
while(par[a].first>=v && par[a].second!=a){
    a=par[a].second;
}
return a;
}
void _union(int a,int b,int v){
int ra,rb;
ra=findr(a,v);
rb=findr(b,v);
if(ra==rb) return;
if(r[ra]<=r[rb]){
    par[ra]=make_pair(v,rb);
    r[rb]=max(r[rb],r[ra]+1);
}
else{
    par[rb]=make_pair(v,ra);
    r[ra]=max(r[ra],r[rb]+1);
}
}
void dijkstra(){
priority_queue < pair<int,int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;
bool mar[maxN];
int i,x;
for(i=0;i<=n;i++){
if(dg[i]==0) pq.push(make_pair(0,i));
mar[i]=false;
}
while(!pq.empty()){
x=pq.top().second;
pq.pop();
if(mar[x]) continue;
//cout<<x<<endl;
mar[x]=true;
for(i=0;i<adj[x].size();i++){
    if(dg[adj[x][i].second]>dg[x]+adj[x][i].first){
       dg[adj[x][i].second]=dg[x]+adj[x][i].first;
       pq.push(make_pair(dg[adj[x][i].second],adj[x][i].second));
    }
}
}
}
bool poredi(edge a,edge b){
return a.w>b.w;
}
bool cmp(int a,int b){
return a>b;}

int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(i=0;i<m;i++){
      cin>>x>>y>>z;
      e[i].v=x;
      e[i].u=y;
      adj[x].push_back(make_pair(z,y));
      adj[y].push_back(make_pair(z,x));
    }
    for(i=0;i<=n;i++){
        dg[i]=INT_MAX;
        par[i]=make_pair(0,i);
        r[i]=0;
    }
    cin>>k;
    for(i=0;i<k;i++){
        cin>>y;
        dg[y]=0;
    }
    dijkstra();
    for(i=1;i<=n;i++){
        p.push_back(dg[i]);
    }
    for(i=0;i<m;i++){
        e[i].w=min(dg[e[i].v],dg[e[i].u]);
    }
    sort(p.begin(),p.end(),cmp);
    sort(e,e+m,poredi);
    for(i=0;i<m;i++){
        _union(e[i].v,e[i].u,e[i].w);
    }
    cin>>q;
    for(i=0;i<q;i++){
        cin>>x>>y;
        int l,d,m;
        l=0; d=n;
        while(l!=d){
            m=(l+d)/2;
            if(findr(x,p[m])==findr(y,p[m])) d=m;
            else l=m+1;
        }
        ans.push_back(p[l]);
    }
    for(i=0;i<q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

plan.cpp: In function 'void dijkstra()':
plan.cpp:48:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(i=0;i<adj[x].size();i++){
         ~^~~~~~~~~~~~~~

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