用线段树套链表维护所有边，用set维护未访问过的点

然后BFS，每次在线段树上找边，然后在set中查询点

一条边使用之后就没有用了，所以在链表中将它删去

时间复杂度$O((n+m)\log n+m\log^2n)$。

 

#include
     
      #include
      
       #include
       
        #define N 500010using namespace std;int n,m,S,i,c,d,x2,y2,x,z,q[N],h,t,f[N],cnt,pos[N];struct Edge{int l,r;Edge*nxt;}*g[1048577],pool[9000000],*cur=pool,*p;set
        
         T;set
         
          ::iterator y,tmp[N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}void build(int x,int a,int b){  if(a==b){pos[a]=x;return;}  int mid=(a+b)>>1;  build(x<<1,a,mid),build(x<<1|1,mid+1,b);}void ins(int x,int a,int b){  if(c<=a&&b<=d){    p=cur++,p->l=x2,p->r=y2,p->nxt=g[x],g[x]=p;    return;  }  int mid=(a+b)>>1;  if(c<=mid)ins(x<<1,a,mid);  if(d>mid)ins(x<<1|1,mid+1,b);}int main(){  read(n),read(m),read(S);  while(m--){    read(c),read(d),read(x2),read(y2),ins(1,1,n);    swap(c,x2),swap(d,y2),ins(1,1,n);  }  build(1,1,n),q[h=t=1]=S;  for(i=1;i<=n+1;i++)if(i!=S)T.insert(i);  while(h<=t)for(z=f[x=q[h++]]+1,x=pos[x];x;g[x]=NULL,x>>=1)for(p=g[x];p;p=p->nxt){    for(cnt=0,y=T.lower_bound(p->l);*y<=p->r;y++)f[q[++t]=*y]=z,tmp[++cnt]=y;    while(cnt)T.erase(tmp[cnt--]);  }  for(i=1;i<=n;i++)printf("%d\n",f[i]);  return 0;}