結果
問題 |
No.3031 曲面の向き付け
|
ユーザー |
![]() |
提出日時 | 2025-02-21 23:03:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,052 ms / 2,000 ms |
コード長 | 1,345 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 82,296 KB |
実行使用メモリ | 223,196 KB |
最終ジャッジ日時 | 2025-02-21 23:03:45 |
合計ジャッジ時間 | 12,710 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 29 |
ソースコード
def compress(arr): *XS, = set(arr) XS.sort() return {cmp_e: cmp_i for cmp_i, cmp_e in enumerate(XS)} m = int(input()) a = [0] * m b = [0] * m c = [0] * m for i in range(m): a[i], b[i], c[i] = map(int,input().split()) v = compress(a + b + c) for i in range(m): a[i] = v[a[i]] b[i] = v[b[i]] c[i] = v[c[i]] e = dict() muki_e = dict() ikeru = [[] for i in range(m)] muki_ikeru = [[] for i in range(m)] def add(x, y, i): ox = x oy = y if x > y: x, y = y, x if (x, y) not in e: e[(x, y)] = [i] if ox < oy: muki_e[(x, y)] = 0 else: muki_e[(x, y)] = 1 return elif len(e[(x, y)]) >= 2: print("NO") exit() if ox < oy: ikeru[e[(x,y)][0]].append((i, muki_e[(x,y)] ^ 1)) ikeru[i].append((e[(x,y)][0], muki_e[(x,y)] ^ 1)) else: ikeru[e[(x,y)][0]].append((i, muki_e[(x,y)])) ikeru[i].append((e[(x,y)][0], muki_e[(x,y)])) e[(x, y)].append(i) for i in range(m): add(a[i], b[i], i) add(b[i], c[i], i) add(c[i], a[i], i) tansaku = [0] * m muki = [0] * m mada = [] for st in range(m): if tansaku[st]: continue tansaku[st] = 1 muki[st] = 0 mada.append(st) while mada: i = mada.pop() for j, c in ikeru[i]: if tansaku[j] == 1: if (muki[i]^muki[j])!=c: print("NO") exit() continue tansaku[j] = 1 mada.append(j) muki[j]=muki[i]^c assert(muki[i]^muki[j])==c print("YES")