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。
题解：
每条边的权值设为它消失的时间。
lct维护最大生成树。lct中维护树边,另开一个集合维护非树边。
从小到达枚举时间进行加边和删边。
对于加边,判断加边是否会形成奇环,并且更新最大生成树和集合.
对于删边，如果是最大生成树里的边就在lct中删掉。否则仅在集合中删掉即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 400010
using namespace std;
int point1[N],point2[N],n,m,T,cnt,size[N],s[N],c[N][2],fa[N],mn[N],v[N];
int in[N],on[N],next[N],rev[N],num,ss,tt;
struct use{int st,en,w;}e[N];
struct use2{int st,en;}b[N];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void add1(int x,int y){next[++cnt]=point1[x];point1[x]=cnt;b[cnt].en=y;}
void add2(int x,int y){next[++cnt]=point2[x];point2[x]=cnt;b[cnt].en=y;}
bool isroot(int x){return c[fa[x]][1]!=x&&c[fa[x]][0]!=x;}
void updata(int x){
int l=c[x][0],r=c[x][1];
size[x]=size[l]+size[r]+(x>n);mn[x]=x;
if (v[mn[x]]>v[mn[l]]) mn[x]=mn[l];
if (v[mn[x]]>v[mn[r]]) mn[x]=mn[r];
}
void pushdown(int x){
int l=c[x][0],r=c[x][1];
if (rev[x]){rev[l]^=1;rev[r]^=1;rev[x]^=1;swap(c[x][0],c[x][1]);}
}
void rotata(int x){
int l,r,y=fa[x],z=fa[y];
if (c[y][0]==x) l=0;else l=1;r=l^1;
if (!isroot(y)){if (c
Description
神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
Input
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这 ...查看全文
[0]==y) c
Description
神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
Input
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这 ...查看全文
[0]=x;else c
Description
神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
Input
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这 ...查看全文
[1]=x;}
fa[x]=z;fa[c[x][r]]=y;fa[y]=x;
c[y][l]=c[x][r];c[x][r]=y;
updata(y);updata(x);
}
void splay(int x){
int top(0);s[++top]=x;
for (int i=x;!isroot(i);i=fa[i]) s[++top]=fa[i];
for (int i=top;i;i--)pushdown(s[i]);
while (!isroot(x)){
int y=fa[x],z=fa[y];
if (!isroot(y)){if (c[y][0]==x^c
Description
神犇有一个n个节点的图。因为神犇是神犇，所以在T时间内一些边会出现后消失。神犇要求出每一时间段内这个图是否是二分图。这么简单的问题神犇当然会做了，于是他想考考你。
Input
输入数据的第一行是三个整数n,m,T。
第2行到第m+1行，每行4个整数u,v,start,end。第i+1行的四个整数表示第i条边连接u,v两个点，这 ...查看全文
[0]==y) rotata(y);else rotata(x);}
rotata(x);
}
}
void access(int x){int t(0);while (x){splay(x);c[x][1]=t;t=x;updata(x);x=fa[x];}}
void makeroot(int x){access(x);splay(x);rev[x]^=1;}
void split(int x,int y){makeroot(y);access(x);splay(x);}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;}
int find(int x){access(x);splay(x);int y=x;while (c[y][0]) y=c[y][0];return y;}
void ins(int x){
int u=e[x].st,v=e[x].en;
if (u==v){in[x]=1;num++;return;}
if(find(u)!=find(v)){on[x]=1;link(u,x+n);link(v,x+n);}
else{
split(u,v);int y=mn[u]-n;
if (e[y].w<e[x].w){
if (size[u]&1^1){in[y]=1;num++;}
cut(e[y].st,y+n);cut(e[y].en,y+n);link(u,x+n);link(v,x+n);
on[y]=0;on[x]=1;
}
else{if (size[u]&1^1) in[x]=1,num++;}
}
}
void del(int x){
if (on[x]){cut(e[x].st,x+n);cut(e[x].en,x+n);}
else if (in[x])num--;
}
int main(){
n=read();m=read();T=read();memset(v,127/3,sizeof(v));
for (int i=1;i<=n;i++) mn[i]=i;
for (int i=1;i<=m;i++){
e[i].st=read();e[i].en=read();ss=read();tt=read();e[i].w=tt;
add1(ss,i);add2(tt,i);size[n+i]=1;v[n+i]=tt;mn[n+i]=n+i;
}
for (int i=0;i<T;i++){
for(int j=point1[i];j;j=next[j]) ins(b[j].en);
for(int j=point2[i];j;j=next[j]) del(b[j].en);
if (!num) puts("Yes");else puts("No");
}
}
|
转播
