Description
神犇有一个 n 个节点的图. 因为神犇是神犇, 所以在 T 时间内一些边会出现后消失. 神犇要求出每一时间段内这个图是否是二分图. 这么简单的问题神犇当然会做了, 于是他想考考你.
Input
输入数据的第一行是三个整数 n,m,T.
第 2 行到第 m+1 行, 每行 4 个整数 u,v,start,end. 第 i+1 行的四个整数表示第 i 条边连接 u,v 两个点, 这条边在 start 时刻出现, 在第 end 时刻消失.
Output
输出包含 T 行. 在第 i 行中, 如果第 i 时间段内这个图是二分图, 那么输出 "Yes", 否则输出 "No", 不含引号.
- Sample Input
- 3 3 3
- 1 2 0 2
- 2 3 0 3
- 1 3 1 2
- Sample Output
- Yes
- No
- Yes
解题思路:
LCT 维护图的连通性很好的一道题.
发现如果是树那么一定可以, 如果奇数环一定不是.
离线一下, 然后维护一颗树中最早被删除的点.
维护最后一条边 (可以用数组存)
最后判一下就好了.
代码:
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #define lll tr[spc].ch[0]
- #define rrr tr[spc].ch[1]
- #define ls ch[0]
- #define rs ch[1]
- using std::swap;
- using std::sort;
- const int E=100005;
- struct trnt{
- int ch[2];
- int fa;
- int lzt;
- int val;
- int mnp;
- int mn;
- int sum;
- int tip;
- bool anc;
- }tr[1000000];
- struct ent{
- int f,t,dl;
- }e[1000000];
- struct Event{
- bool cmd;
- int f,t,tpc;
- int no;
- }ev[1000000];
- int n,m,T;
- int num;
- int cnt;
- bool onr[1000000];
- bool odd[1000000];
- bool whc(int spc)
- {
- return tr[tr[spc].fa].rs==spc;
- }
- void pushup(int spc)
- {
- tr[spc].sum=tr[spc].val;
- tr[spc].mn=tr[spc].tip;
- tr[spc].mnp=spc;
- if(lll)
- {
- tr[spc].sum+=tr[lll].sum;
- if(tr[spc].mn>tr[lll].mn)
- {
- tr[spc].mn=tr[lll].mn;
- tr[spc].mnp=tr[lll].mnp;
- }
- }
- if(rrr)
- {
- tr[spc].sum+=tr[rrr].sum;
- if(tr[spc].mn>tr[rrr].mn)
- {
- tr[spc].mn=tr[rrr].mn;
- tr[spc].mnp=tr[rrr].mnp;
- }
- }
- return ;
- }
- void trr(int spc)
- {
- if(!spc)
- return ;
- tr[spc].lzt^=1;
- swap(lll,rrr);
- return ;
- }
- void pushdown(int spc)
- {
- if(tr[spc].lzt)
- {
- tr[spc].lzt=0;
- trr(lll);
- trr(rrr);
- }
- return ;
- }
- void recal(int spc)
- {
- if(!tr[spc].anc)
- recal(tr[spc].fa);
- pushdown(spc);
- return ;
- }
- void rotate(int spc)
- {
- int f=tr[spc].fa;
- bool k=whc(spc);
- tr[f].ch[k]=tr[spc].ch[!k];
- tr[spc].ch[!k]=f;
- if(tr[f].anc)
- {
- tr[spc].anc=1;
- tr[f].anc=0;
- }else
- tr[tr[f].fa].ch[whc(f)]=spc;
- tr[spc].fa=tr[f].fa;
- tr[f].fa=spc;
- tr[tr[f].ch[k]].fa=f;
- pushup(f);
- pushup(spc);
- return ;
- }
- void splay(int spc)
- {
- recal(spc);
- while(!tr[spc].anc)
- {
- int f=tr[spc].fa;
- if(tr[f].anc)
- {
- rotate(spc);
- return ;
- }
- if(whc(spc)^whc(f))
- rotate(spc);
- else
- rotate(f);
- rotate(spc);
- }
- return ;
- }
- void access(int spc)
- {
- int lst=0;
- while(spc)
- {
- splay(spc);
- tr[rrr].anc=1;
- tr[lst].anc=0;
- rrr=lst;
- pushup(spc);
- lst=spc;
- spc=tr[spc].fa;
- }
- return ;
- }
- void Mtr(int spc)
- {
- access(spc);
- splay(spc);
- trr(spc);
- return ;
- }
- void split(int x,int y)
- {
- Mtr(x);
- access(y);
- splay(y);
- return ;
- }
- int finf(int spc)
- {
- access(spc);
- splay(spc);
- while(lll)
- spc=lll;
- return spc;
- }
- void link(int x,int y)
- {
- Mtr(x);
- tr[x].fa=y;
- return ;
- }
- void cut(int x,int y)
- {
- split(x,y);
- tr[x].fa=tr[y].ls=0;
- tr[x].anc=1;
- pushup(y);
- return ;
- }
- void Insert(int frm,int twd,int spc,int Time)
- {
- if(frm==twd)
- {
- num++;
- odd[spc]=true;
- return ;
- }
- Mtr(frm);
- if(finf(twd)==frm)
- {
- int x=tr[twd].mnp-E;
- if(e[x].dl<Time)
- {
- onr[x]=false;
- onr[spc]=true;
- if(tr[twd].sum%2==0)
- {
- odd[x]=true;
- num++;
- }
- cut(e[x].f,x+E);
- cut(e[x].t,x+E);
- link(frm,spc+E);
- link(twd,spc+E);
- }else{
- if(tr[twd].sum%2==0)
- {
- odd[spc]=true;
- num++;
- }
- }
- }else{
- link(frm,spc+E);
- link(twd,spc+E);
- onr[spc]=true;
- }
- return ;
- }
- void Delete(int frm,int twd,int spc)
- {
- if(onr[spc])
- {
- cut(frm,spc+E);
- cut(twd,spc+E);
- onr[spc]=false;
- return ;
- }
- if(odd[spc])
- {
- odd[spc]=false;
- num--;
- }
- return ;
- }
- bool cmp(Event x,Event y)
- {
- return x.tpc<y.tpc;
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&T);
- for(int i=1;i<=n;i++)
- {
- tr[i].anc=1;
- tr[i].tip=0x3f3f3f3f;
- }
- for(int i=1;i<=m;i++)
- {
- int a,b,c,d;
- scanf("%d%d%d%d",&a,&b,&c,&d);
- ev[++cnt]=(Event){0,a,b,c,i};
- ev[++cnt]=(Event){1,a,b,d,i};
- e[i]=(ent){a,b,d};
- int spc=i+E;
- tr[spc].anc=1;
- tr[spc].mn=d;
- tr[spc].tip=d;
- tr[spc].mnp=i;
- tr[spc].val=1;
- }
- sort(ev+1,ev+cnt+1,cmp);
- for(int i=1,hpn=1;i<=T;i++)
- {
- for(;(hpn<=cnt)&&(ev[hpn].tpc<i);hpn++)
- {
- Event x=ev[hpn];
- if(!x.cmd)
- Insert(x.f,x.t,x.no,e[x.no].dl);
- else
- Delete(x.f,x.t,x.no);
- }
- if(num)
- puts("No");
- else
- puts("Yes");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2883327.html