首页 > 代码库 > bzoj2035: [2009国家集训队]数据读取问题

bzoj2035: [2009国家集训队]数据读取问题

Description

技术分享

Input

技术分享

Output

技术分享

可以转为边权为1的最短路:将不修改并读取x个数看作有向边,原先树上的边仍保留且视为双向边(但从根出发的边为单向)表示上次读取的修改

第一种边是点到bfs序的一个区间区间连边,用并查集维护bfs序中每个位置下一个未处理的位置即可

为了求出这个bfs序区间,需要知道一个点向左下(右下)走x步到达的点,将树上每个点和其最左(右)孩子间的边保留,删去其它边,得到一些链,维护每个点在链上的位置即可支持询问

求bfs序区间可以做到O(n),bfs由于用到并查集需要O(nlogn)或O(nα(n)),I/O为瓶颈需要O(nlogn)时间

#include<cstdio>const int N=1e6+77;int mem[N],*mp=mem;int n,*e[N][2],v[N],fa[N];int f[N],q[N],ql=0,qr=0;int lq[N],rq[N],bq[N];int id[N][2],bid[N],lp=0,rp=0,F[N];int gf(int x){    while(x!=F[x])x=F[x]=F[F[x]];    return x;}void chk(int w,int d){    if(f[w]>=0)return;    f[w]=d;    q[++qr]=w;    if(e[w][0]==e[w][1])printf("%d\n",d);}void pre(){    ql=qr=0;    bq[bid[1]=++qr]=1;    while(ql!=qr){        int w=bq[++ql];        if(!id[w][0])for(int x=w;;x=e[x][0][0]){            lq[id[x][0]=++lp]=x;            if(e[x][0]==e[x][1])break;        }        if(!id[w][1])for(int x=w;;x=e[x][1][-1]){            rq[id[x][1]=++rp]=x;            if(e[x][0]==e[x][1])break;        }        for(int*a=e[w][0],*b=e[w][1];a!=b;bq[bid[*a]=++qr]=*a,++a);    }}int _(){    int x;    scanf("%d",&x);    return x;}int main(){    n=_();    for(int i=1;i<=n+1;++i)F[i]=i;    for(int i=1;i<=n;++i)f[i]=-1;    for(int w=1,c;w<=n;++w){        v[w]=_();        c=_();        for(int j=0;j<c;++j)fa[mp[j]=_()]=w;        e[w][0]=mp;        mp+=c;        e[w][1]=mp;    }    pre();    ql=qr=0;    chk(1,0);    while(ql!=qr){        int w=q[++ql],u,d=f[w]+1;        for(int*a=e[w][0],*b=e[w][1];a!=b;++a){            u=*a;            if(w!=1)chk(u,d);            for(int L=gf(bid[lq[id[u][0]+v[u]]]),R=bid[rq[id[u][1]+v[u]]];L<=R;chk(bq[L],d),L=F[L]=gf(L+1));        }        if(w!=1)chk(fa[w],d);    }    return 0;}

 

bzoj2035: [2009国家集训队]数据读取问题