首页 > 代码库 > bzoj4025 二分图

bzoj4025 二分图

2024-10-03 09:30:39   210人阅读

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。

 

正解：$CDQ$分治+并查集。

这类题都是一个套路。把在区间$[l,r]$内恒出现的边连起来，然后使用带权并查集判断是否为奇环即可。

注意连边的一些细节，比如说点权需要改成$dep[u] \ xor \ dep[v] \ xor 1$，还有就是撤回的时候连上去的那个点深度设为$0$。

 

 1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <queue>10 #include <stack>11 #include <map>12 #include <set>13 #define inf (1<<30)14 #define N (500010)15 #define ls (x<<1)16 #define rs (x<<1|1)17 #define il inline18 #define RG register19 #define ll long long20 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)21 22 using namespace std;23 24 struct node{ int x,y,a,h; }st[20000010];25 struct edge{ int u,v; }g[N];26 27 vector <int> mp[4*N];28 29 int h[N],a[N],dep[N],fa[N],sz[4*N],n,m,T,cnt,top;30 31 il int gi(){32     RG int x=0,q=1; RG char ch=getchar();33     while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar();34     if (ch==‘-‘) q=-1,ch=getchar();35     while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar();36     return q*x;37 }38 39 il void query(RG int x,RG int l,RG int r,RG int xl,RG int xr,RG int v){40     if (xl<=l && r<=xr){ ++sz[x],mp[x].push_back(v); return; } RG int mid=(l+r)>>1;41     if (xr<=mid) query(ls,l,mid,xl,xr,v);42     else if (xl>mid) query(rs,mid+1,r,xl,xr,v);43     else query(ls,l,mid,xl,mid,v),query(rs,mid+1,r,mid+1,xr,v); return;44 }45 46 il int find(RG int x){47     if (fa[x]==x) return x; RG int y=find(fa[x]);48     dep[x]=dep[fa[x]]^a[x]; return y;49 }50 51 il int unionn(RG int u,RG int v){52     RG int x=find(u),y=find(v); if (h[x]>h[y]) swap(x,y),swap(u,v);53     if (x==y) return dep[u]^dep[v]^1; st[++top]=(node){x,y,a[x],h[y]};54     fa[x]=y,a[x]=dep[u]^dep[v]^1; if (h[x]==h[y]) ++h[y]; return 0;55 }56 57 il void del(RG int now){58     for (;top>now;--top){59     fa[st[top].x]=st[top].x,dep[st[top].x]=0;60     a[st[top].x]=st[top].a,h[st[top].y]=st[top].h;61     }62     return;63 }64 65 il void solve(RG int x,RG int l,RG int r){66     RG int mid=(l+r)>>1,now=top;67     for (RG int i=0,j,res;i<sz[x];++i){68     j=mp[x][i],res=unionn(g[j].u,g[j].v);69     if (res){ for (RG int i=l;i<=r;++i) puts("No"); del(now); return; }70     }71     if (l==r){ puts("Yes"),del(now); return; }72     solve(ls,l,mid),solve(rs,mid+1,r),del(now); return;73 }74 75 il void work(){76     n=gi(),m=gi(),T=gi(); for (RG int i=1;i<=n;++i) fa[i]=i,h[i]=a[i]=1;77     for (RG int i=1,u,v,l,r;i<=m;++i){78     u=gi(),v=gi(),l=gi()+1,r=gi(); if (l>r) continue;79     g[++cnt].u=u,g[cnt].v=v,query(1,1,T,l,r,cnt);80     }81     solve(1,1,T); return;82 }83 84 int main(){85     File("grape");86     work();87     return 0;88 }

 

bzoj4025 二分图


联系
我们