結果

問題 No.3031 曲面の向き付け
ユーザー shobonvip
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0