CF576E

发布时间:2016-12-31 7:13:54编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"CF576E ",主要涉及到CF576E 方面的内容,对于CF576E 感兴趣的同学可以参考一下。

*在#里发他一直WA这道CF题,然后我就去看了看,感觉还挺有趣的,那我就在这里整理一下我的思路..毕竟一边听歌..

题意: 给个图,每条边初始无色,每次给一个询问(e,c)表示把e涂成颜色c,如果此时颜色c组成的子图是一个二分图就涂色并输出YES,否则回撤这个操作并输出NO.(offline available)

其实加边删边维护联通性的时候我们维护一棵最大删除时间生成树,关于二分图判定的部分其实只需要检查一条边两端点在生成树上的距离的奇偶性就好了.然而这个做法是离线的,我们没法知道这个最大删除时间是多少..

先考虑在线做法: 动态图连通性的在线做法加上维护树形态的LCT查询链长度就可以了,不过空间复杂度为nlog^2n不是很可以接受啊..

我们考虑用每条边的预计删除时间(<=删除时间)代替删除时间做,每次执行询问(e,c)的时候先查询可行性,要是不可行的话我们可以发现这条e的预计最大删除时间被延长了(被延长到下一次删除),如果可行的话我们就直接加入这条边.因为这条边的预计最大删除时间是只增不减的所以维护的时候不会出现什么鬼畜问题了..

然后感觉需要处理一些小细节..?那就这样吧..

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MM=500500,MN=500500;struct sn;typedef sn*sp;sp n;struct ed;struct dt;struct ed{int u,v,c;dt*d;}E[MM];struct dt{ed*e;int r;sp u,v,w;}P[MM]={{E,MM,0,0,0}},*dp=P;struct qr{int c;dt*r;}Q[MM];#define ms(a,b) (b->r<a->r?b:a)#define ts(a,b) (b->r<a->r?a=b:a)struct sn{    sp c[2],f,t;    dt*v,*m;    int r,s;    void U(){m=ms(c[0]->m,c[1]->m),ts(m,v),s=c[0]->s+c[1]->s+(v==P);}    void R(){r^=1,swap(c[0],c[1]);}    void D(){r?c[0]->R(),c[1]->R(),r=0:0;}    void J(int z){        sp F=f;F->D(),D(),t=F->t,(f=F->f)->c[F->f->c[1]==F]=this;        c[!z]=(F->c[z]=c[!z])->f=F;F->f=this;F->U();    }    void S(){        D();for(int z;f!=n;)            f->f!=n?(f->c[1]==this)==(z=f->f->c[1]==f)?f->J(z):J(!z),J(z):J(f->c[1]==this);        U();    }    void E(sp z=n){        S();if(c[1]!=n)c[1]->t=this,c[1]->f=n;        (c[1]=z)->f=this,U();    }}tr[MM*3],*tp=tr+1;sp A(sp b){for(b->E();b->t;b=b->t)b->t->E(b);return b;}sp Z(sp b){return (b=A(b))->R(),b;}sp W(sp b){for(b->S();b->c[0]!=n;b=b->c[0])b->D();return b->S(),b;}void L(sp u,sp v){Z(u)->t=v;}void B(sp u,sp v){u->E(),v->E(),(u->t==v?u:v)->t=0;}sp nd[55][MN],el[MM];sp M(int c,int i){return !nd[c][i]?*(nd[c][i]=tp)=(sn){n,n,n,0,P,P,0,1},tp++:nd[c][i];}int main(){    (n=tr)->v=P,n->m=P;int N,m,C,q;scanf("%d%d%d%d",&N,&m,&C,&q);    for(int i=1;i<=m;++i)scanf("%d%d",&E[i].u,&E[i].v);    for(int i=1;i<=q;++i)        scanf("%d%d",&N,&C),E[N].d?E[N].d->r=i-1:0,(E[N].d=++dp)->e=E+N,Q[i]=(qr){C,dp};    for(int i=1;i<=m;++i)E[i].d?E[i].d->r=q:0;    for(int i=1,_;i<=q;++i){        dt*m,*c=Q[i].r;        sp u=M(C=Q[i].c,c->e->u),v=M(C,c->e->v),w=(Z(u),A(v));        m=w->m,_=w->s;        if(W(w)==u){            if(m->r>=i&&_&1){                if(puts("NO"),!(C=c->e->c))continue;                if((m=c->e->d)->w){B(m->u,m->w),B(m->v,m->w),m->w=0;goto ln;}                else{Z(u=m->u),m=(w=A(m->v))->m;if(W(w)!=u)goto ln;goto ct;}            }puts("YES");            ct:if(m->r<c->r)B(m->u,m->w),B(m->v,m->w),m->w=0;            else{c->e->c=C,c->e->d=c,c->w=0,c->u=M(C,c->e->u),c->v=M(C,c->e->v);continue;}        }else puts("YES");        ln:c->e->d=c,c->e->c=C,*(c->w=tp)=(sn){n,n,n,0,c,c,0,0};        L(tp,c->u=M(C,c->e->u)),L(tp++,c->v=M(C,c->e->v));    }return 0;


上一篇:开刷LeetCode
下一篇:sqlalchemy学习

相关文章

关键词: CF576E

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款