40分求调qaq
查看原帖
40分求调qaq
1283833
_Persever_ance楼主2024/7/20 22:04
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
long long int t, n, tot , b[200010], fa[200010];
vector<pair<int, int>>vec;
struct qaq {
	int x, y, e;
}nd[100005];

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c>'9')	{ if (c == '-')	f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

int bisect(int x)
{
	int l = 1, r = tot;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (b[mid] >= x)	r = mid;
		else l = mid + 1;
	}
	return l;
}

void init(int tot)
{
	for (int i = 1; i <= tot; i++)
		fa[i] = i;
}

int get(int x)
{
	return x == fa[x] ? x : fa[x] = get(fa[x]);
}

void U(int x, int y)
{
	fa[get(x)] = get(y);
}
int main()
{
	t = read();
	while (t--)
	{
		vec.clear();
		memset(nd, 0, sizeof(nd));
		memset(b, 0, sizeof(b));
		memset(fa, 0, sizeof(fa));
		n = read();
		tot = 0;
		

		for (int i = 1; i <= n; i++)
		{
			nd[i].x = read(); nd[i].y = read(); nd[i].e = read();
			b[++tot] = nd[i].x;
			b[++tot] = nd[i].y;
		}
		sort(b + 1, b + tot + 1);
		tot = unique(b + 1, b + tot + 1) - b - 1;
		init(tot);
		for (int i = 1; i <= n; i++)
		{
			nd[i].x = bisect(nd[i].x);
			nd[i].y = bisect(nd[i].y);
		}

		for (int i = 1; i <= n; i++)
		{
			if (nd[i].e)
				U(nd[i].x, nd[i].y);
			else
			{
				vec.push_back(make_pair(nd[i].x, nd[i].y));
			}
		}

		int flag = 0;
		for (vector<pair<int, int>>::iterator it = vec.begin(); it != vec.end(); it++)
			if (get(it->first) == get(it->second))
			{
				cout << "NO" << endl;
				flag = 1;
			}
		if(flag==0)	cout << "YES" << endl;
	}
	return 0;
}
2024/7/20 22:04
加载中...