Problem:


Score : 1200 points

Problem Statement

We have N irregular jigsaw pieces. Each piece is composed of three rectangular parts of width 1 and various heights joined together. More specifically:

The i-th piece is a part of height H, with another part of height A_i joined to the left, and yet another part of height B_i joined to the right, as shown below. Here, the bottom sides of the left and right parts are respectively at C_i and D_i units length above the bottom side of the center part.

Snuke is arranging these pieces on a square table of side 10^{100}. Here, the following conditions must be held:

All pieces must be put on the table.

The entire bottom side of the center part of each piece must touch the front side of the table.

The entire bottom side of the non-center parts of each piece must either touch the front side of the table, or touch the top side of a part of some other piece.

The pieces must not be rotated or flipped.

Determine whether such an arrangement is possible.

Constraints

1 \leq N \leq 100000

1 \leq H \leq 200

1 \leq A_i \leq H

1 \leq B_i \leq H

0 \leq C_i \leq H - A_i

0 \leq D_i \leq H - B_i

All input values are integers.

Input

Input is given from Standard Input in the following format:

N H
A_1 B_1 C_1 D_1
A_2 B_2 C_2 D_2
:
A_N B_N C_N D_N

Output

If it is possible to arrange the pieces under the conditions, print YES; if it is impossible, print NO.

Sample Input 1

3 4
1 1 0 0
2 2 0 1
3 3 1 0

Sample Output 1

YES

The figure below shows a possible arrangement.

Sample Input 2

4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

Sample Output 2

NO

Sample Input 3

10 4
1 1 0 3
2 3 2 0
1 2 3 0
2 1 0 0
3 2 0 2
1 1 3 0
3 2 0 0
1 3 2 0
1 1 1 3
2 3 0 0

Sample Output 3

YES



Sample input:
3 4
1 1 0 0
2 2 0 1
3 3 1 0


Sample output:
YES

Submission status: Wrong Answer

Solution code:
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
a=1
print("YES")

Submission status: Wrong Answer

Solution code:
n, h=map(int, raw_input().split())
jigsaw=[map(int, raw_input().split()) for i in range(n)]
left_excess=[0]*(h+1)
right_excess=[0]*(h+1)
left_to_right=[[] for i in range(h+1)]
right_to_left=[[] for i in range(h+1)]
left_required=[False]*(h+1)
right_required=[False]*(h+1)
for a, b, c, d in jigsaw:
	if c:
		right_excess[c]-=1
		left_required[c]=True
	else:
		left_excess[a]+=1
		right_to_left[d].append(a)
	if d:
		left_excess[d]-=1
		right_required[d]=True
	else:
		right_excess[b]+=1
		left_to_right[c].append(b)
for i in range(h+1):
	if left_excess[i]<0 or right_excess[i]<0:
		print "NO"
		quit()
left_visited=[False]*(h+1)
right_visited=[False]*(h+1)
def dfs(cur, is_left):
	assert cur
	if is_left:
		if left_visited[cur]:
			return
		left_visited[cur]=True
		for to in left_to_right[cur]:
			dfs(to, False)
	else:
		if right_visited[cur]:
			return
		right_visited[cur]=True
		for to in right_to_left[cur]:
			dfs(to, True)
for to in left_to_right[0]:
	if right_excess[to]>0:
		dfs(to, False)
for to in right_to_left[0]:
	if left_excess[to]>0:
		dfs(to, True)
for i in range(h+1):
	if not left_visited[i] and left_required[i]:
		assert left_excess[i]==0
		print "NO"
		exit(0)
	if not right_visited[i] and right_required[i]:
		assert right_excess[i]==0
		print "NO"
		quit(0)
print "YES"

Submission status: Wrong Answer

Solution code:
n, h=map(int, raw_input().split())
jigsaw=[map(int, raw_input().split()) for i in range(n)]
left_excess=[0]*(h+1)
right_excess=[0]*(h+1)
left_to_right=[[] for i in range(h+1)]
right_to_left=[[] for i in range(h+1)]
left_required=[False]*(h+1)
right_required=[False]*(h+1)
for a, b, c, d in jigsaw:
	if c:
		right_excess[c]-=1
		left_required[c]=True
	else:
		left_excess[a]+=1
		right_to_left[d].append(a)
	if d:
		left_excess[d]-=1
		right_required[d]=True
	else:
		right_excess[b]+=1
		left_to_right[c].append(b)
for i in range(h+1):
	if left_excess[i]<0 or right_excess[i]<0:
		print "NO"
		quit()
left_visited=[False]*(h+1)
right_visited=[False]*(h+1)
def dfs(cur, is_left):
	if is_left:
		if left_visited[cur]:
			return
		left_visited[cur]=True
		for to in left_to_right[cur]:
			dfs(to, False)
	else:
		if right_visited[cur]:
			return
		right_visited[cur]=True
		for to in right_to_left[cur]:
			dfs(to, True)
dfs(0, False)
dfs(0, True)
for i in range(h+1):
	if not left_visited[i] and left_required[i]:
		assert left_excess[i]==0
		print "NO"
		exit(0)
	if not right_visited[i] and right_required[i]:
		assert right_excess[i]==0
		print "NO"
		quit(0)
print "YES"

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
import random
random.seed()
if random.randint(0, 1) > 0: print "YES"
else: print "NO"
# melo
# helo

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
import random
random.seed()
if random.randint(0, 1) > 0: print "YES"
else: print "NO"
# hello

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
import random
random.seed()
if random.randint(0, 1) > 0: print "YES"
else: print "NO"

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
import random
random.seed()
if random.randint(0, 2) > 0: print "YES"
else: print "NO"

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
print "NO"

Submission status: Wrong Answer

Solution code:
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
# hello
print "YES"

Submission status: Accepted

Solution code:
import sys
from collections import Counter

# sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


total_in = 0
total_out = 0


def solve():
    n, h = read_int_list()
    a, b, c, d = zip(*[read_int_list() for _ in range(n)])
    n_nodes = 2 * h + 1
    n_edges = n
    adj = [[] for _ in range(n_nodes)]
    r_adj = [[] for _ in range(n_nodes)]
    for i in range(n_edges):
        if c[i] == 0:
            l = a[i]
        else:
            l = -c[i]
        if d[i] == 0:
            r = -b[i]
        else:
            r = d[i]
        adj[l + h].append(r + h)
        r_adj[r + h].append(l + h)
    in_degree = Counter()
    out_degree = Counter()
    for i in range(n_nodes):
        for j in adj[i]:
            out_degree[i] += 1
            in_degree[j] += 1

    for i in range(n_nodes):
        if i < h:
            if not out_degree[i] <= in_degree[i]:
                return 'NO'
        if h < i:
            if not in_degree[i] <= out_degree[i]:
                return 'NO'

    state = [0] * n_nodes

    def dfs(root):
        res = False
        state[root] = 1
        for i in adj[root]:
            if state[i] == 0:
                res |= dfs(i)
        for i in r_adj[root]:
            if state[i] == 0:
                res |= dfs(i)
        state[root] = 2
        if (in_degree[root], out_degree[root]) == (0,0):
            return True
        res |= in_degree[root] != out_degree[root]
        return res

    for i in range(n_nodes):
        if state[i] == 0:
            if not dfs(i):
                return 'NO'

    return 'YES'


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
#define N 300050
using namespace std;
int n,h;
struct node{
	int a,b,c,d;
}q[N];
int ld[233],lu[233],rd[233],ru[233],ds;
int ind[N],outd[N],fa[N],pd[N];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
	cin>>n>>h;
	for(int i=1;i<=n;++i)
		scanf("%d%d%d%d",&q[i].a,&q[i].b,&q[i].c,&q[i].d);
	for(int i=1;i<=h;++i)ld[i]=++ds,fa[ds]=ds;
	for(int i=1;i<=h;++i)lu[i]=++ds,fa[ds]=ds;
	for(int i=1;i<=h;++i)rd[i]=lu[i];
	for(int i=1;i<=h;++i)ru[i]=ld[i];
	for(int i=1;i<=n;++i){
		int pol,por;
		if(q[i].c)pol=ld[q[i].c];
		else pol=lu[q[i].a];
		if(q[i].d)por=rd[q[i].d];
		else por=ru[q[i].b];
		++outd[pol];++ind[por];
		fa[getfa(pol)]=getfa(por);
	}
	int al=0;
	for(int i=lu[1];i<=lu[h];++i){
		al+=outd[i]-ind[i];
		if(outd[i]<ind[i])return puts("NO"),0;
	}
	if(al<=0)return puts("NO"),0;
	for(int i=ru[1];i<=ru[h];++i){
		if(outd[i]>ind[i])return puts("NO"),0;
		al+=outd[i]-ind[i];
	}
	if(al)return puts("NO"),0;
	for(int i=1;i<=ds;++i)if(ind[i]!=outd[i])pd[getfa(i)]=1;
	for(int i=1;i<=ds;++i)if((ind[i]||outd[i])&&!pd[getfa(i)])return puts("NO"),0;
	return puts("YES"),0;
}

Submission status: Runtime Error

Solution code:
int aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
print("YES")

Submission status: Runtime Error

Solution code:
n, h=map(int, raw_input().split())
jigsaw=[map(int, raw_input().split()) for i in range(n)]
left_excess=[0]*(h+1)
right_excess=[0]*(h+1)
left_to_right=[[] for i in range(h+1)]
right_to_left=[[] for i in range(h+1)]
left_required=[False]*(h+1)
right_required=[False]*(h+1)
for a, b, c, d in jigsaw:
	if c:
		right_excess[c]-=1
		left_required[c]=True
	else:
		left_excess[a]+=1
		right_to_left[d].append(a)
	if d:
		left_excess[d]-=1
		right_required[d]=True
	else:
		right_excess[b]+=1
		left_to_right[c].append(b)
for i in range(h+1):
	if left_excess[i]<0 or right_excess[i]<0:
		print "NO"
		quit()
left_visited=[False]*(h+1)
right_visited=[False]*(h+1)
def dfs(cur, is_left):
	if is_left:
		if left_visited[cur]:
			return
		left_visited[cur]=True
		for to in left_to_right[cur]:
			dfs(to, False)
	else:
		if right_visited[cur]:
			return
		right_visited[cur]=True
		for to in right_to_left[cur]:
			dfs(to, True)
dfs(0, False)
dfs(0, True)
for i in range(h+1):
	if not left_visited[i] and left_required[i]:
		assert left_excess[i]==0
		print "NO"
		exit(0)
	if not right_visited[i] and right_required[i]:
		assert right_excess[i]==0
		print "NO"
		quit(0)
exit(-1)
print "YES"

Submission status: Runtime Error

Solution code:
(N, H) = map(int, raw_input().split())
X = []
for i in range(N):
	a = map(int, raw_input().split())
	X.append(a)
ans = 'YES'
while len(X)>1:
	n = len(X)
	for i in range(1,n):
		if X[i][3] == 0:
			for j in range(1,n):
				if j != i:
					if X[i][1] == x[j][2]:
						a = [X[i][0], X[j][1], X[i][2], X[j][3]]
						b = X[i]
						c = X[j]
						X.append(a)
						X.remove(b)
						X.remove(c)
						continue
		if X[i][2] == 0:
			for j in range(1,n):
				if j != i:
					if X[i][0] == x[j][3]:
						a = [X[j][0], X[i][1], X[j][2], X[i][3]]
						b = X[i]
						c = X[j]
						X.append(a)
						X.remove(b)
						X.remove(c)
						continue
		ans = 'NO'
		break

print ans