求条
查看原帖
求条
1446545
XHZnewlife楼主2025/7/3 19:52
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int root;
int bxj[200010];
int cnt=0;
struct EDGE{
	int x,y;
	bool operator<(const EDGE &b)const{
		if(x!=b.x)return x<b.x;
		else return y<b.y;
	}
};
stack<EDGE> cx;
map <EDGE,int> num;
int find(int x){
	if(bxj[x]==x)return x;
	else return find(bxj[x]);
}
bool unionn(int x,int y){
	int p=100000;
	if(find(x)!=find(y)){
		cx.push({find(x),find(y)});
		num[cx.top()]++;
		bxj[find(x)]=find(y+p);
		bxj[find(y)]=find(x+p);
		return true;
	}
	else{
		return false;
	}
}
void slipt(int x,int y){
	int p=100000;
	bxj[x]=x,bxj[y]=y;
	return;
}
struct tree{
	int fa;
	int left,right;
	int lid,rid;
	vector<EDGE> edge;
}leaf[400005];
int build_tree(int l,int r,int fa){
	int id=++cnt;
	leaf[id].fa=fa;
	leaf[id].left=l,leaf[id].right=r;
	if(l==r){
		return id;
	}
	int mid=(l+r)/2;
	leaf[id].lid=build_tree(l,mid,id);
	leaf[id].rid=build_tree(mid+1,r,id);
	return id;
}
void add_edge(int x,int y,int l,int r,int id){
	if(leaf[id].right<=r and leaf[id].left>=l){
		leaf[id].edge.push_back({x,y});
		return;
	}
	int mid=(leaf[id].left+leaf[id].right)>>1;
	if(mid>=l)add_edge(x,y,l,r,leaf[id].lid);
	if(mid<r)add_edge(x,y,l,r,leaf[id].rid);
	return;
}
void dfs(int id,bool bl){
	for(auto i:leaf[id].edge){
		if(!unionn(i.x,i.y))bl=0;
	}
	if(leaf[id].left!=leaf[id].right){
		dfs(leaf[id].lid,bl);
		dfs(leaf[id].rid,bl);
	}
	else{
		if(bl)cout<<"Yes"<<'\n';
		else cout<<"No"<<'\n';
	}
	for(int i=0;i<leaf[id].edge.size();i++){
		if(!(--num[cx.top()]))slipt(cx.top().x,cx.top().y);
		cx.pop();
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	root=build_tree(1,k,cnt);
	for(int i=1,x,y,l,r;i<=m;i++){
		cin>>x>>y>>l>>r;
		add_edge(x,y,l,r,root);
	}
	dfs(root,1);
	return 0;
}

第一次学,没有完全学会

2025/7/3 19:52
加载中...