超出内存是什么情况,我数组开的不大啊
查看原帖
超出内存是什么情况,我数组开的不大啊
126334
jr_tat楼主2020/9/26 10:00
#include <bits/stdc++.h>
using namespace std; 
int f[200001]={0};
int get(int a){
	if(f[a]==a)return a;
	else return f[a]=get(f[a]);
}
int a[200001],b[200001],e[200001],x,y,z,lsh[200001]={0}; 
int fi,ta;
int as,bs;
void solve(){
	bool pd=1;
    int m;
   	cin>>m;
	//离散化
	priority_queue <int> sor;
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(e,0,sizeof(e));
	memset(lsh,0,sizeof(lsh));
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		sor.push(x);
		sor.push(y);
		a[i]=x;
		b[i]=y;
		e[i]=z;
	}
	int l=0;
	while(!sor.empty()){
		int d=sor.top();
		sor.pop();
		if(l==0||d!=lsh[l]){
			l++;
			lsh[l]=d;
		}
	}
	/*/check 
	for(int i=1;i<=l;i++){
		cout<<lsh[i]<<endl;
	}
	*/
   	for(int i=1;i<=l;i++){
   		f[i]=i;
		}
	for(int i=1;i<=m;i++){
		//find a
		fi=1,ta=l;
		while(fi<ta){
			int mid=(fi+ta)>>1;
			if(lsh[mid]>=a[i])ta=mid;
			else fi=mid+1;
		}
		as=fi;
		//
		//find b 
		fi=1,ta=l;
		while(fi<ta){
			int mid=(fi+ta)/2;
			if(lsh[mid]>=b[i])ta=mid;
			else fi=mid+1;
		}
		bs=fi;
		//
		if(e[i]==1){
			if(f[as]==as||f[bs]==bs){
				f[as]=bs;
	    	}
	    	else if(get(as)!=get(bs)){
		    	pd=0;
				break;
		   	}
     	}
	    if(e[i]==0){
		   	if(get(as)==get(bs)){
				pd=0;
				break;
			}
		}
   	}
	if(pd==1){
		cout<<"YES"<<endl;
	}
	else cout<<"NO"<<endl;	
} 
int main(int argc, char** argv) {
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
   		solve();
	}
	return 0;
}
2020/9/26 10:00
加载中...