并查集+离散化50pts求助
查看原帖
并查集+离散化50pts求助
313137
qqqqq111楼主2022/7/14 16:42

rt

#include <cstdio>
#include <cstring>
#include <algorithm>

namespace IO {
	typedef long long ll;
	inline ll rad() {
		int f=1;
		ll x=0;
		char c=getchar();
		while(c<'0' || c>'9') {
			if(c=='-')
				f=-1;
			c=getchar();
		}
		while(c>='0' && c<='9') {
			x=(x<<1)+(x<<3)+(c^48);
			c=getchar();
		}
		return x*f;
	}
	inline void write(ll x, char c='\n') {
		if(x) {
			if(x<0) {
				x=-x;
				putchar('-');
			}
			char bit[30];
			short l=0;
			for(; x; x/=10)
				bit[l++]=x%10^48;
			for(l--; l>=0; l--) 
				putchar(bit[l]);
		}
		else 
			putchar('0');
		putchar(c);
	}
}

using namespace IO;

#define N 1000005

int n;
int fa[N];
int pro[N*2], c[N*2], b[N*2];
int op[N];
int cnt;

int fnd(int x) {
	return fa[x]==x? x:fa[x]=fnd(fa[x]);
}
void merge(int x, int y) {
	int fx=fnd(x), fy=fnd(y);
	if(fx!=fy)
		fa[fx]=fy;
}

int main() {
	int T=rad(),m;
	while(T--) {
		memset(pro, 0, sizeof(pro));
		memset(c, 0, sizeof(c));
		memset(b, 0, sizeof(b));
		memset(op, 0, sizeof(op));
		n=rad();
		for(int i=1; i<=n<<1; i++)
			fa[i]=i;
		cnt=0;
		bool ans=true;
		for(int i=1; i<=n; i++) {
			pro[++cnt]=rad(), c[cnt]=pro[cnt]; pro[++cnt]=rad(), c[cnt]=pro[cnt];
			op[i]=rad();
		}
		// write(cnt);
		// for(int i=1; i<=cnt; i++)
		// 	write(pro[i], ' ');
		std::sort(c+1, c+cnt+1);
		m=std::unique(c+1, c+cnt+1)-c-1;
		for(int i=1; i<=m; i++) {
			b[i]=std::lower_bound(c+1, c+m+1, pro[i])-c;
//			write(b[i], ' ');
		}//input and dis

		for(int i=1, j=1; i<=n; i++) {
			if(op[i]==1) {
				int t=b[j];++j;
				merge(t, b[j]);
				j++;
			}
		}
		for(int i=1, j=1; i<=n; i++) {
			if(!op[i]) {
				int t=b[j];++j;
				if(fnd(t)==fnd(b[j])) { 
					j++;
					ans=false;
					break;
				}
			}
		} 
		puts(ans? "YES":"NO");
			//write(ans);
	}
	return 0;
}
2022/7/14 16:42
加载中...