注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4025]二分图  

2015-05-14 15:30:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4025: 二分图

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 88  Solved: 23
[Submit][Status][Discuss]

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

HINT

样例说明:
0时刻,出现两条边1-2和2-3。
第1时间段内,这个图是二分图,输出Yes。
1时刻,出现一条边1-3。
第2时间段内,这个图不是二分图,输出No。
2时刻,1-2和1-3两条边消失。
第3时间段内,只有一条边2-3,这个图是二分图,输出Yes。
数据范围:
n<=100000,m<=200000,T<=100000,1<=u,v<=n,0<=start<=end<=T。

Solution

LCT维护奇环
对于新加进来的边有下面2种情况:
1.把两个联通块合并->直接link,不对答案造成影响;
2. 形成一个环->将环上最早将要被踢掉的点拿出来,如果当前形成的环是奇环则cnt++,把这条边打上标记。
删除的话,只要cnt-=该边标记即可,还有一个cut。ans=[cnt==0]

Code

/**************************************************************
    Problem: 4025
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:7272 ms
    Memory:20732 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#define N 300010
int n,m,t,rev[N],siz[N],fa[N],son[N][2],val[N],min[N],ala[N],dla[N],flag[N],out[N],ans,i;
struct E{int x,y,l,r,an,dn;}e[N];
#define ls son[t][0]
#define rs son[t][1]
#define nr(t) (son[fa[t]][0]==t||son[fa[t]][1]==t)
void pd(int t){
    if(rev[t])rev[t]=0,rev[ls]^=1,rev[rs]^=1,std::swap(ls,rs);
}
void pu(int t){
    siz[t]=siz[ls]+siz[rs]+1;
    min[t]=e[min[ls]].r<e[min[rs]].r?min[ls]:min[rs];
    if(e[min[t]].r>e[val[t]].r)min[t]=val[t];
}
void rtt(int t){
    int f=fa[t],p=son[f][1]==t;
    fa[t]=fa[f],nr(f)?son[fa[f]][son[fa[f]][1]==f]=t:1,
    (son[f][p]=son[t][p^1])?fa[son[f][p]]=f:1,
    pu(son[fa[f]=t][p^1]=f);
}
void pv(int t){
    if(nr(t))pv(fa[t]);pd(t);
}
void splay(int t){int f;
    for(pv(t);nr(t);rtt(t))
    if(f=fa[t],nr(f))rtt(son[f][1]==t^son[fa[f]][1]==f?t:f);pu(t);
}
void access(int t){
    for(int las=0;t;splay(t),rs=las,las=t,t=fa[t]);
}
#define mkr(t) (access(t),splay(t),rev[t]^=1)
#define link(u,v) (mkr(u),fa[u]=v)
#define cut(u,v) (mkr(u),access(v),splay(v),fa[u]=son[v][0]=0)
int fdr(int t){
    while(nr(t))t=fa[t];return t;
}
void add(int p){
    mkr(e[p].x),access(e[p].y);splay(e[p].y);
    if(fdr(e[p].x)!=fdr(e[p].y)){
        link(e[p].x,p+n);
        link(p+n,e[p].y);
    }
    else{
        int p0=min[e[p].y];
        if(e[p0].r<e[p].r){
            cut(e[p0].x,p0+n);
            cut(p0+n,e[p0].y);
            link(e[p].x,p+n);
            link(p+n,e[p].y);
            p=p0;
        }
        out[p]=1;mkr(e[p].x),access(e[p].y),splay(e[p].y);
        if(((siz[e[p].y]+1)>>1)&1)flag[p]=1;ans+=flag[p];
    }
}
void del(int p){
    if(!out[p]){
        mkr(e[p].x),access(e[p].y),splay(e[p].y);
        if(fdr(e[p].x)==fdr(e[p].y))cut(e[p].x,p+n),cut(p+n,e[p].y);
    }
    else ans-=flag[p];
}
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
int main(){
    scanf("%d%d%d",&n,&m,&t);e[0].r=t+1;
    for(i=1;i<=n+m;i++)siz[i]=1;
    for(i=1;i<=m;i++){
        e[i]=(E){F(),F(),F(),F()};
        e[i].an=ala[e[i].l];ala[e[i].l]=i;
        e[i].dn=dla[e[i].r];dla[e[i].r]=i;
        min[i+n]=val[i+n]=i;
    }
    for(i=0;i<t;i++){
        for(;ala[i];ala[i]=e[ala[i]].an)add(ala[i]);
        for(;dla[i];dla[i]=e[dla[i]].dn)del(dla[i]);
        puts(ans?"No":"Yes");
    }
}
  评论这张
 
阅读(71)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018