文件详细信息

下载本文件

本文件的大小为 1583 字节。

#include<cstdio>
#include<vector>
void read(int&num){
	int ch=getchar();
	num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
}
template<typename T>
inline void swap(T&a,T&b){
	T temp=a;
	a=b;
	b=temp;
}
const int maxn=100005,maxm=200005;
int n,m,k;
struct Edge{
	int x,y;
}e[maxm];
int fa[maxn<<1],h[maxn<<1];
int find(int x){
	while(x!=fa[x])x=fa[x];
	return x;
}
struct Data{
	int x,y,add;
}stack[maxn*20];
int x,y,add,top;
void merge(int x,int y){
	x=find(x),y=find(y);
	if(h[x]>h[y])swap(x,y);
	stack[++top]=Data{x,y,h[x]==h[y]};
	fa[x]=y;
	if(h[x]==h[y])h[y]++;
}
std::vector<int>T[maxn<<2];
int ql,qr,id;
void modify(int u,int l,int r){
	if(ql<=l&&r<=qr){
		T[u].push_back(id);
		return;
	}
	int m=(l+r)>>1;
	if(ql<=m)modify(u<<1,l,m);
	if(qr>m)modify(u<<1|1,m+1,r);
}
void solve(int u,int l,int r){
	int ans=1,last_top=top;
	for(int i:T[u]){
		int a=find(e[i].x),b=find(e[i].y);
		if(a==b){
			for(int i=l;i<=r;i++)puts("No");
			ans=0;
			break;
		}
		int c=find(e[i].x+n),d=find(e[i].y+n);
		merge(a,d);
		merge(b,c);
	}
	if(ans){
		if(l==r)puts("Yes");
		else{
			int m=(l+r)>>1;
			solve(u<<1,l,m);
			solve(u<<1|1,m+1,r);
		}
	}
	while(top>last_top){
		x=stack[top].x,y=stack[top].y,add=stack[top].add;
		h[fa[x]]-=add;
		fa[x]=x;
		top--;
	}
}
int main(){
	read(n),read(m),read(k);
	for(int i=1;i<=(n<<1);i++)fa[i]=i;
	for(int i=1;i<=(n<<1);i++)h[i]=1;
	int u,v,l,r;
	for(int i=1;i<=m;i++){
		read(u),read(v),read(l),read(r);
		e[i].x=u,e[i].y=v;
		ql=l+1,qr=r,id=i;
		modify(1,1,k);
	}
	solve(1,1,k);
	return 0;
}