結果

問題 No.3031 曲面の向き付け
ユーザー shobonvip
提出日時 2025-02-21 23:03:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,052 ms / 2,000 ms
コード長 1,345 bytes
コンパイル時間 379 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 223,196 KB
最終ジャッジ日時 2025-02-21 23:03:45
合計ジャッジ時間 12,710 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compress(arr):
	*XS, = set(arr)
	XS.sort()
	return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)}


m = int(input())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
	a[i], b[i], c[i] = map(int,input().split())

v = compress(a + b + c)
for i in range(m):
	a[i] = v[a[i]]
	b[i] = v[b[i]]
	c[i] = v[c[i]]

e = dict()
muki_e = dict()
ikeru = [[] for i in range(m)]
muki_ikeru = [[] for i in range(m)]

def add(x, y, i):
	ox = x
	oy = y
	
	if x > y:
		x, y = y, x
	
	if (x, y) not in e:
		e[(x, y)] = [i]
		if ox < oy: muki_e[(x, y)] = 0
		else: muki_e[(x, y)] = 1
		return
	elif len(e[(x, y)]) >= 2:
		print("NO")
		exit()
	
	if ox < oy:
		ikeru[e[(x,y)][0]].append((i, muki_e[(x,y)] ^ 1))
		ikeru[i].append((e[(x,y)][0], muki_e[(x,y)] ^ 1))
	else:
		ikeru[e[(x,y)][0]].append((i, muki_e[(x,y)]))
		ikeru[i].append((e[(x,y)][0], muki_e[(x,y)]))
	
	e[(x, y)].append(i)


for i in range(m):
	add(a[i], b[i], i)
	add(b[i], c[i], i)
	add(c[i], a[i], i)

tansaku = [0] * m
muki = [0] * m
mada = []

for st in range(m):
	if tansaku[st]: continue
	tansaku[st] = 1
	muki[st] = 0
	mada.append(st)
	while mada:
		i = mada.pop()
		for j, c in ikeru[i]:
			if tansaku[j] == 1:
				if (muki[i]^muki[j])!=c:
					print("NO")
					exit()
				continue
			tansaku[j] = 1
			mada.append(j)
			muki[j]=muki[i]^c
			assert(muki[i]^muki[j])==c

print("YES")
0