結果
問題 |
No.3031 曲面の向き付け
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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")