結果
問題 | No.3031 曲面の向き付け |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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] = xreturn xdef unite(self, x, y):x, y = self.find(x), self.find(y)if x == y:returnif self.data[x] > self.data[y]:x, y = y, xself.data[x] += self.data[y]self.data[y] = xreturndef 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 = 1000000000S = 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]] = iE = [[] 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:continueif uf.find(u) != u:continuestack = [u]color[u] = 0while stack:v = stack.pop()for w in G[v]:if color[w] == -1:color[w] = color[v] ^ 1stack.append(w)elif color[w] == color[v]:print("NO")exit()else:continueprint("YES")