結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー nikoro256
提出日時 2025-02-21 23:16:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,282 ms / 2,000 ms
コード長 1,426 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 204,116 KB
最終ジャッジ日時 2025-02-21 23:17:00
合計ジャッジ時間 15,382 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
from collections import deque
M=int(input())
dic=defaultdict(list)
dat=[]
l=[[] for _ in range(M)]
for i in range(M):
    A,B,C=map(int,input().split())
    dat.append((A,B,C))
    l[i]=[[A,B],[B,C],[C,A]]
    dic[(A,B)].append(i)
    dic[(B,C)].append(i)
    dic[(A,C)].append(i)
edge=[[] for _ in range(M)]
for k in dic.keys():
    if len(dic[k]) >= 3:
        print("NO")
        exit()
    if len(dic[k]) == 1:
        continue
    p=dic[k][0]
    p2=dic[k][1]
    se=set(dat[p])&set(dat[p2])
    if len(l)==3:
        sel=list(se)
        use = [[sel[0],sel[1]],[sel[1],sel[2]],[sel[2],sel[0]]]
    else:
        sel=list(se)
        use = [[sel[0],sel[1]]]
    for a,b in use:
        #print(a,b,l[p],l[p2],int([a,b] in l[p] ),int( [a,b] in l[p2]))
        if int([a,b] in l[p] )^int( [a,b] in l[p2])==0:
            edge[p].append((p2,-1))
            edge[p2].append((p,-1))
        else:
            edge[p].append((p2,1))
            edge[p2].append((p,1))
di=[0 for _ in range(M)]
for i in range(M):
    if di[i]==0:
        di[i]=1
        dq=deque([i])
        while len(dq)!=0:
            p = dq.popleft()
            for e,o in edge[p]:
                if di[e]==0:
                    di[e]=di[p]*o
                    dq.append(e)
                else:
                    if di[e]!=di[p]*o:
                        print("NO")
                        exit()
print("YES")
0