結果
| 問題 | No.2293 無向辺 2-SAT |
| ユーザー |
 t98slider
|
| 提出日時 | 2023-03-16 08:09:22 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 1,947 bytes |
| コンパイル時間 | 664 ms |
| コンパイル使用メモリ | 82,336 KB |
| 実行使用メモリ | 848,916 KB |
| 最終ジャッジ日時 | 2024-05-02 03:46:18 |
| 合計ジャッジ時間 | 6,954 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 45 ms
53,504 KB |
| testcase_01 | AC | 55 ms
64,256 KB |
| testcase_02 | AC | 47 ms
53,888 KB |
| testcase_03 | MLE | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
ソースコード
from sys import stdin
from collections import deque
class UnionFind():
def __init__(self, n):
self.N = n
self.siz = n
self.parent_or_size = [-1] * n
self.stack = deque()
self.used_list = []
def leader(self, x):
if self.parent_or_size[x] < 0: return x
self.stack.append(x)
x = self.parent_or_size[x]
while self.parent_or_size[x] >= 0:
self.stack.append(self.parent_or_size[x])
x = self.parent_or_size[x]
while len(self.stack):
self.parent_or_size[self.stack.pop()] = x
return x
def same(self, x, y):
return self.leader(x) == self.leader(y)
def merge(self, x, y):
rx, ry = self.leader(x), self.leader(y)
if rx == ry: return
if self.parent_or_size[rx] > self.parent_or_size[ry]: rx, ry = ry, rx
self.parent_or_size[rx] += self.parent_or_size[ry]
self.parent_or_size[ry] = rx
self.siz -= 1
self.used_list.append(rx)
self.used_list.append(ry)
def reset(self):
self.siz = self.N
for pos in self.used_list:
self.parent_or_size[pos] = -1
self.used_list.clear()
N, Q = map(int, input().split())
is_zero = 0
uf = UnionFind(2 * N)
pow2 = [0] * (N + 1)
pow2[0] = 1
for i in range(N): pow2[i + 1] = (pow2[i] + pow2[i]) % 998244353
for _ in range(Q):
query = list(map(int, stdin.readline().split()))
if query[0] <= 2:
query[1] -= 1
query[2] -= 1
if query[0] == 1:
uf.merge(query[1], query[2])
uf.merge(query[1] + N, query[2] + N)
else:
uf.merge(query[1], query[2] + N)
uf.merge(query[1] + N, query[2])
if uf.same(query[1], query[1] + N): is_zero = 1
else:
is_zero = 0
uf.reset()
if is_zero == 1:
print(0)
else:
print(pow2[uf.siz >> 1])