結果
問題 | No.2277 Honest or Dishonest ? |
ユーザー |
|
提出日時 | 2023-04-21 23:13:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 575 ms / 2,000 ms |
コード長 | 1,113 bytes |
コンパイル時間 | 411 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 84,124 KB |
最終ジャッジ日時 | 2024-11-08 06:44:00 |
合計ジャッジ時間 | 22,621 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
n, q = map(int, input().split()) uf = [-1]*(2*n) def root(a): if uf[a] < 0: return a uf[a] = root(uf[a]) return uf[a] def same(a, b): return root(a) == root(b) def merge(a, b): if same(a, b): return a = root(a) b = root(b) if uf[b] < uf[a]: a, b = b, a uf[a] += uf[b] uf[b] = a def sizeof(a): return -uf[a] mod = 998244353 for _ in range(q): a, b, c = map(int, input().split()) # 各人 2頂点用意する # A B 0 のとき A0->B0, A1->B1に辺 # A B 1 のとき A0->B1, A1->B0に辺 # やって、A0とA1が同じ頂点で矛盾 (A0と仮定してA1が導かれるのが矛盾) a -= 1 b -= 1 if c == 0: merge(a, b) merge(a + n, b + n) else: merge(a, b + n) merge(a + n, b) if same(a, a + n): print(0) else: ch = [0] * (n * 2) ans = 1 for i in range(n): r0 = root(i) r1 = root(i + n) if ch[r0] > 0 or ch[r1] > 0: continue ch[r0] = 1 ch[r1] = 1 ans = ans * 2 % mod print(ans)