結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー titia
提出日時 2025-06-24 05:56:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,183 ms / 2,000 ms
コード長 1,939 bytes
コンパイル時間 369 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 174,104 KB
最終ジャッジ日時 2025-06-24 05:57:08
合計ジャッジ時間 12,580 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from collections import defaultdict

M=int(input())
X=[list(map(int,input().split())) for i in range(M)]

D=defaultdict(list)

for i in range(M):
    x,y,z=X[i]

    D[x,y].append(i)
    D[y,z].append(i)
    D[x,z].append(i)

for d in D:
    if len(D[d])>=3:
        print("NO")
        exit()
        
USE=[-1]*M

for i in range(M):
    if USE[i]!=-1:
        continue

    USE[i]=0
    Q=[i]
    while Q:
        ind=Q.pop()
        x,y,z=X[ind]

        if len(D[x,y])==2:
            if D[x,y][0]==ind:
                ind2=D[x,y][1]
            else:
                ind2=D[x,y][0]

            x2,y2,z2=X[ind2]

            if x2==x and z2==y:
                u2=USE[ind]
            else:
                u2=USE[ind]^1

            if USE[ind2]!=-1 and USE[ind2]!=u2:
                print("NO")
                exit()
            if USE[ind2]==-1:
                USE[ind2]=u2
                Q.append(ind2)

        if len(D[y,z])==2:
            if D[y,z][0]==ind:
                ind2=D[y,z][1]
            else:
                ind2=D[y,z][0]

            x2,y2,z2=X[ind2]

            if x2==y and z2==z:
                u2=USE[ind]
            else:
                u2=USE[ind]^1

            if USE[ind2]!=-1 and USE[ind2]!=u2:
                print("NO")
                exit()
            if USE[ind2]==-1:
                USE[ind2]=u2
                Q.append(ind2)

        if len(D[x,z])==2:
            if D[x,z][0]==ind:
                ind2=D[x,z][1]
            else:
                ind2=D[x,z][0]

            x2,y2,z2=X[ind2]

            if x2==x and z2==z:
                u2=USE[ind]^1
            else:
                u2=USE[ind]

            if USE[ind2]!=-1 and USE[ind2]!=u2:
                print("NO")
                exit()
            if USE[ind2]==-1:
                USE[ind2]=u2
                Q.append(ind2)


print("YES")
0