結果

問題 No.3031 曲面の向き付け
コンテスト
ユーザー PNJ
提出日時 2025-02-21 23:22:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,162 ms / 2,000 ms
コード長 2,241 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 177,124 KB
最終ジャッジ日時 2025-02-21 23:22:26
合計ジャッジ時間 14,545 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind():
  def __init__(self, n):
    self.data = [-1 for i in range(n)]
  
  def find(self, x):
    stack = []
    while self.data[x] >= 0:
      stack.append(x)
      x = self.data[x]
    while len(stack):
      y = stack.pop()
      self.data[y] = x
    return x
  
  def unite(self, x, y):
    x, y = self.find(x), self.find(y)
    if x == y:
      return
    if self.data[x] > self.data[y]:
      x, y = y, x
    self.data[x] += self.data[y]
    self.data[y] = x
    return
  
  def same(self, x, y):
    return self.find(x) == self.find(y)
  
  def size(self, x):
    return -self.data[self.find(x)]

M = int(input())
B = 1000000000
S = set()
V = []
for i in range(M):
  a, b, c = map(int, input().split())
  S.add(a + B * b)
  S.add(a + B * c)
  S.add(b + B * c)
  V.append((a, b, c))

S = list(S)
S.sort()
d = {}
for i in range(len(S)):
  d[S[i]] = i
E = [[] for _ in range(len(S))]
EE = [[] for _ in range(len(S))]
GG = [[] for u in range(M)]
uf = UnionFind(M)
for u in range(M):
  a, b, c = V[u]
  j = d[a + B * b]
  if len(E[j]) + len(EE[j]) >= 2:
    print("NO")
    exit()
  if len(E[j]) == 1:
    v = E[j][0]
    GG[u].append(v)
    GG[v].append(u)
  if len(EE[j]) == 1:
    v = EE[j][0]
    uf.unite(u, v)
  E[j].append(u)
  j = d[b + B * c]
  if len(E[j]) + len(EE[j]) >= 2:
    print("NO")
    exit()
  if len(E[j]) == 1:
    v = E[j][0]
    GG[u].append(v)
    GG[v].append(u)
  if len(EE[j]) == 1:
    v = EE[j][0]
    uf.unite(u, v)
  E[j].append(u)
  j = d[a + B * c]
  if len(E[j]) + len(EE[j]) >= 2:
    print("NO")
    exit()
  if len(EE[j]) == 1:
    v = EE[j][0]
    GG[u].append(v)
    GG[v].append(u)
  if len(E[j]) == 1:
    v = E[j][0]
    uf.unite(u, v)
  EE[j].append(u)

G = [[] for u in range(M)]
for u in range(M):
  r = uf.find(u)
  for v in GG[u]:
    G[r].append(uf.find(v))

# 二部グラフ判定
color = [-1 for _ in range(M)]
for u in range(M):
  if color[u] != -1:
    continue
  if uf.find(u) != u:
    continue
  stack = [u]
  color[u] = 0
  while stack:
    v = stack.pop()
    for w in G[v]:
      if color[w] == -1:
        color[w] = color[v] ^ 1
        stack.append(w)
      elif color[w] == color[v]:
        print("NO")
        exit()
      else:
        continue
print("YES")
0