bzoj3073: [Pa2011]Journeys

#include<bits/stdc++.h>
char buf[10000007],*ptr=buf-1;
int _(){
    int x=0,c=*++ptr;
    while(c<48)c=*++ptr;
    while(c>47)x=x*10+c-48,c=*++ptr;
    return x;
}
int n,m,k,mx=2;
int l[2555555],idp;
bool d[2555555],ev[30000007];
int es[30000007],enx[30000007],e0[2555555],ep=2;
void ae(int a,int b,int c){
    es[ep]=b;enx[ep]=e0[a];ev[ep]=c;e0[a]=ep++;
}
void ins1(int l,int r,int w){
    for(l+=mx-1,r+=mx+1;l^r^1;l>>=1,r>>=1){
        if(~l&1)ae(l^1,w,1);
        if(r&1)ae(r^1,w,1);
    }
}
void ins2(int l,int r,int w){
    for(l+=mx-1,r+=mx+1;l^r^1;l>>=1,r>>=1){
        if(~l&1)ae(w,(l^1)+mx*2,1);
        if(r&1)ae(w,(r^1)+mx*2,1);
    }
}
std::deque<int>q;
int main(){
    fread(buf,1,sizeof(buf),stdin);
    n=_();m=_();k=_();
    while(mx<n+1)mx<<=1;
    idp=mx*4+1;
    for(int i=mx-1;i;--i){
        ae(i<<1,i,0),ae(i<<1^1,i,0);
        ae(mx*2+i,mx*2+(i<<1),0),ae(mx*2+i,mx*2+(i<<1^1),0);
    }
    for(int i=1;i<mx*2;++i)ae(i+mx*2,i,0);
    for(int i=0,a,b,c,d;i<m;++i){
        a=_();b=_();c=_();d=_();
        ++idp;
        ins1(a,b,idp);
        ins2(c,d,idp);
        ++idp;
        ins1(c,d,idp);
        ins2(a,b,idp);
    }
    memset(l,0x3f,sizeof(int)*(idp+2));
    q.push_back(k+mx);l[k+mx]=0;
    while(!q.empty()){
        int w=q.front();q.pop_front();
        if(d[w])continue;
        d[w]=1;
        for(int i=e0[w];i;i=enx[i]){
            int u=es[i];
            if(ev[i]){
                if(l[u]>l[w]+1)l[u]=l[w]+1,q.push_back(u);
            }else{
                if(l[u]>l[w])l[u]=l[w],q.push_front(u);
            }
        }
    }
    for(int i=1;i<=n;++i)printf("%d\n",l[i+mx]>>1);
    return 0;
}