题目翻译传送门

这题其实十分的妙，尽管代码很短，但确实对得起它紫题的难度。

看到这样的一道题，首先一个很自然的想法就是按照能拼上的关系建图，然后通过一个神奇的方式找到一条路径。

但这样一来光建图就需要 $\mathcal O(n^2)$ 的时间，没有办法满足题目的需要。然后发现虽然 $n$ 很大，但是 $H$ 是很小的，那么下一个想法是，能不能使用 $H$ 进行建图。

然后就有一个很妙的转换方式，其它题解里讲了一些转换为负的方法，很妙，其实不用这样，还得去处理负下标的问题，只需要确保两种会被映射到不相交的区间里就可以了，所以这样转化就可以了：

• 若 $d > 0$, 则 $r = d$, 否则 $r = b+h$。
• 若 $c > 0$, 则 $l = c+h$ 否则 $l = a$。

经过这样的转换，右边的若和左边可以相接，它们就会变成一个一样的值，然后就可以用一条边来表示一块积木，这样边数和点数都在一个可接受的范围内。

然后就是要到若干条路径从小于 $h$ 的点到大于 $h$ 的点并经过所有边的问题了，找到经过每一条边的路径那么直接就可以想到欧拉回路，但这题目中不要求回到原点，也不一定是全部连通的（对应原来的积木中不一定全部是以凹凸的方式拼接的），所以又有了一个很巧妙的构造方式。

建立一个新的点，对于要构造的每一段路径将这个新点和它起点相连，在把终点与新点相连，然后找到一条欧拉回路，在把这新脸上的边和点给去掉就可以了。

所以可以根据欧拉回路要求满足的条件来判断是否能构造成功。有向图有欧拉回路的条件是每个点入度等于出度。

1. 对于小于 $h$ 的点， 入度要小于等于出度，因为构造的时候还要和新点连边， 但不一定是最多只能小 $1$ 因为我们要找出若干条路径而不一定只有一条。
2. 对于大于 $h$ 的点同理。
3. 每一块至少得有一个点入度出度不相等，因为全相等了再和新点连边就没有欧拉回路了。

满足以上条件的就可以按上面数的构造出来，不满足的就肯定 No 了。

代码。

#include <cstdio>
const int H = 405;
int n, h, fa[H], a, b, c, d, l, r, in[H], out[H], ok[H];
int find(int x) {
	if(x != fa[x]) fa[x] = find(fa[x]);
	return fa[x];
}
int main() {
	scanf("%d%d", &n, &h);
	for(int i = 1; i <= 2*h; i++) fa[i] = i;
	for(int i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(d) r = d; else r = b+h;
		if(c) l = c+h; else l = a;
		out[l] ++, in[r] ++;
		int fx = find(l), fy = find(r);
		if(fx == fy) continue;
		fa[fx] = fy;
	}
	for(int i = 1; i <= h; i++) if(in[i] > out[i]) return puts("NO"), 0;
	for(int i = h+1; i <= 2*h; i++) if(in[i] < out[i]) return puts("NO"), 0;
	for(int i = 1; i <= 2*h; i++) if(in[i] != out[i] || !in[i] && !out[i]) ok[find(i)] = 1;
	for(int i = 1; i <= 2*h; i++) if(fa[i] == i && !ok[i]) return puts("NO"), 0;
	puts("YES");
	return 0;
}