求调or证伪or hack(并查集神奇做法0分)
查看原帖
求调or证伪or hack(并查集神奇做法0分)
1130462
180700553dd楼主2025/1/31 23:28
#include <iostream>
using namespace std;
const int N = 2e5 + 5;
int fa[N], dis[N][2];
int d[N];
int n, m, q;
void init(){
	for(int i = 1;i <= n;i++){
		fa[i] = i;
		dis[i][0] = 1;
	}
}
int find(int x){
	if(x != fa[x]){
		int f = fa[x];
		fa[x] = find(fa[x]);
		int a = dis[x][0], b = dis[x][1];
		if(dis[f][0] && a || dis[f][1] && b){
			dis[x][0] = 1;
		}else dis[x][0] = 0;
		if(dis[f][1] && a || dis[f][0] && b){
			dis[x][1] = 1;
		}else dis[x][1] = 0;
	} 
	return fa[x];
}
void uni(int x, int y){
	int rx = find(x), ry = find(y);
	if(rx == ry){
		dis[x][0] |= dis[y][1];
		dis[x][1] |= dis[y][0];
		dis[y][0] |= dis[x][1];
		dis[y][1] |= dis[x][0];  
	}else{
		fa[rx] = ry;
		dis[rx][0] = dis[y][1];
		dis[rx][1] = dis[y][0];
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> q;
	init();
	for(int i = 1;i <= m;i++){
		int u, v;
		cin >> u >> v;
		uni(u, v);
		d[u]++;
		d[v]++;
//		for(int i = 1;i <= n;i++){
//			find(i);
//			cout << i << ' ' << fa[i] << ' ' << dis[i][0] << ' ' << dis[i][1] << '\n';
//		}
//		cout << ":::::::::::\n";
	}
	for(int i = 1;i <= q;i++){
		int x, y, k;
		cin >> x >> y >> k;
		if(find(x) != find(y)){
			cout << "expand\n";
			continue;
		}
		if(x == y && d[x] == 0 && k != 0){
			cout << "expand\n";
			continue;
		}
		if(k & 1){
			if(dis[x][0] && dis[y][1] || dis[x][1] && dis[y][0]){
				cout << "tribool\n";
			}else cout << "expand\n";
		}else{
			if(dis[x][0] && dis[y][0] || dis[x][1] && dis[y][1]){
				cout << "tribool\n";
			}else cout << "expand\n";
		}
	}
	return 0;
}
2025/1/31 23:28
加载中...