結果

問題 No.2277 Honest or Dishonest ?
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:42:42
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 169 ms / 2,000 ms
コード長 1,195 bytes
コンパイル時間 213 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 115,148 KB
最終ジャッジ日時 2025-03-20 20:43:00
合計ジャッジ時間 9,203 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(1 << 25)

def main():
    MOD = 998244353
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1

    parent = list(range(N + 1))  # 1-based
    parity = [0] * (N + 1)
    component_count = N
    contradiction = False

    def find(u):
        path = []
        while parent[u] != u:
            path.append(u)
            u = parent[u]
        root = u
        for v in reversed(path):
            orig_parent = parent[v]
            parent[v] = root
            parity[v] ^= parity[orig_parent]
        return root

    for _ in range(Q):
        A = int(input[ptr])
        ptr +=1
        B = int(input[ptr])
        ptr +=1
        C = int(input[ptr])
        ptr +=1

        ra = find(A)
        rb = find(B)
        pa = parity[A]
        pb = parity[B]

        if ra != rb:
            component_count -= 1
            parent[ra] = rb
            parity[ra] = pa ^ pb ^ C
        else:
            if (pa ^ pb) != C:
                contradiction = True

    if contradiction:
        print(0)
    else:
        print(pow(2, component_count, MOD))

if __name__ == "__main__":
    main()
0