扩展域寄了

#include<iostream>
#define int long long
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif
#define maxn 200005

using namespace std;

int n, m, k, f[8005], a, b, c, d;

int find(int x) {
	if(x == f[x]) return x;
	return f[x] = find(f[x]);
}

bool mge(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx == fy) return true;
	f[fx] = fy;
	return false;
}

void work() {
	cin >> n >> m >> k;
	if(n > 2000 || m > 2000) while(true);
	for(int i = 1; i <= 8000; i++) {
		f[i] = i;
	}
	for(int i = 1; i <= k; i++) {
		cin >> a >> b >> c >> d;
		int e = min(b, d) + 2000;
		if(b > d) {
			mge(a, e);
		}
		else {
			mge(a, e + 4000);
		}
 	}
	for(int i = 1; i <= n; i++) {
		if(find(i) == find(i + 4000)) {
			cout << "NO\n";
			return ;
		}
	}
	for(int i = 1; i <= m; i++) {
		if(find(i + 2000) == find(i + 6000)) {
			cout << "NO\n";
			return ;
		}
	}
	cout << "YES\n";
}

signed main() {
	int _;
	cin >> _;
	while(_--) work();
}

但染色过了。

#include<iostream>
#include<cstring>
#define int long long
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif
#define maxn 200005

using namespace std;

int n, m, k, h[4005], a, b, c1, d, en, c[4005];

struct edge {
	int v, w, next;
} e[8005];
void add(int u, int v, int w) {
	e[en] = (edge){v, w, h[u]};
	h[u] = en++;
}
bool color(int x, int cl) {
	if(c[x] != 0) {
		return cl == c[x];
	}
	c[x] = cl;
	bool flag = true;
	for(int j = h[x]; ~j; j = e[j].next) {
		flag = flag && color(e[j].v, cl * e[j].w);
	}
	return flag;
}

void work() {
	memset(h, 0xff, sizeof(h));
	memset(c, 0, sizeof(c));
	en = 0;
	cin >> n >> m >> k;
	if(n > 2000 || m > 2000) while(true);
	for(int i = 1; i <= k; i++) {
		cin >> a >> b >> c1 >> d;
		int e = min(b, d) + 2000;
		if(b > d) {
			add(a, e, 1);
			add(e, a, 1);
		}
		else {
			add(a, e, -1);
			add(e, a, -1);
		}
 	}
 	bool flag = true;
 	for(int i = 1; i <= 4000; i++) {
 		if(c[i] == 0) {
 			flag = flag && color(i, 1);
		}
	}
	if(flag) cout << "YES\n";
	else cout << "NO\n";
}

signed main() {
	int _;
	cin >> _;
	while(_--) work();
}

为啥？