自写二分函数离散化,90分求助!!!!!!!!!
查看原帖
自写二分函数离散化,90分求助!!!!!!!!!
959579
xiaobu_dean楼主2023/9/19 13:18
#include <bits/stdc++.h>
using namespace std;

using ll = long long ;

const int N = 1e7 + 50;
int fa[N];
int book[N];
int new_n;
struct node {
	int a,b,e;
	bool operator< (const node a) const {
		return e > a.e;
	}
}p[N];

int check(int a) { // 找a或后继的板子
	int l = 0,r = new_n;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (book[mid] == a) return mid;
		if (book[mid] >= a) r = mid;
		else l = mid + 1; 
	}
	return r;
}
void init(int n) { // 初始化
	for (int i = 1;i <= n; i++) {
		fa[i] = i;
	}
}
int find(int x) {
	if (x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}

void add(int a,int b) {
	int fx = find(a); int fy = find(b);
	if (fx != fy) {
		fa[fx] = fy;
	}
}
void solve() {
	memset(fa,0,sizeof(fa));
	memset(book,0,sizeof(book));
	memset(p,0,sizeof(p));
	int n; cin >> n;
	int c = 0;
	for (int i = 1;i <= n; i++) {
		cin >> p[i].a >> p[i].b >> p[i].e;
		book[c++] = p[i].a;
		book[c++] = p[i].b;
	}
	// 离散化
	sort(book + 1,book + c + 1);
	new_n = unique(book + 1,book + c + 1) - (book + 1); // 去重
	for (int i = 1;i <= n; i++) { // 生成新数组
		//p[i].a = lower_bound(book + 1,book + new_n + 1,p[i].a) - book;
		//p[i].b = lower_bound(book + 1,book + new_n + 1,p[i].b) - book;
		p[i].a = check(p[i].a);
		p[i].b = check(p[i].b);
	}
	init(new_n); // 初始化
	sort(p + 1,p + n + 1); // 按e排序,先合并再判断
	for (int i = 1;i <= n; i++) {
		if (p[i].e) {
			add(p[i].a,p[i].b);
		}
		else {
			if (find(p[i].a) == find(p[i].b)) {
				puts("NO");
				return ;
			}
		}
	}
	puts("YES");
}
int main() {
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}
2023/9/19 13:18
加载中...