刷题记录表

#include<bits/stdc++.h>
using namespace std;
inline int read(int &a){a=0;int f=1;char c=getchar();if(c==EOF) return a=EOF;
for(;c<'0' || c>'9';c=getchar()){if(c=='-') f=-1;if(c==EOF) return a=EOF;}
for(;c<='9' && c>='0';a=a*10+c-'0',c=getchar());return a*=f;}
int n,h;
int a[100010],b[100010],c[100010],d[100010];
int fa[100010],s[100010];
int cd[100010],rd[100010];

int reg(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=reg(fa[x]);
}

bool pd()
{
	for(int i=-h;i<=-1;i++)
	if(rd[i+h]>cd[i+h]) return 0;
	for(int i=1;i<=h;i++)
	if(rd[i+h]<cd[i+h]) return 0;
	for(int i=-h;i<=h;i++)
	{
		if(rd[i+h]!=cd[i+h]) s[reg(i+h)]=1;
		else if(rd[i+h]+cd[i+h]==0) s[reg(i+h)]=1;
	}
	for(int i=-h;i<=h;i++)
	if(!s[reg(i+h)]) return 0;
	return 1;
}

int main()
{
	freopen("jigsaw.in","r",stdin);
	freopen("jigsaw.out","w",stdout);
	read(n),read(h);
	for(int i=0;i<=1000;i++) fa[i]=i;
	for(int i=1;i<=n;i++)
	{
		read(a[i]),read(b[i]),read(c[i]),read(d[i]);
		int x=(c[i]?h+c[i]:h-a[i]),y=(d[i]?h-d[i]:h+b[i]);
		cd[x]++,rd[y]++;
		fa[reg(x)]=reg(y);
	}
	if(pd()) puts("YES");
	else puts("NO");
	return 0;
}