結果
問題 | No.2293 無向辺 2-SAT |
ユーザー |
![]() |
提出日時 | 2023-05-05 22:40:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,205 ms / 4,000 ms |
コード長 | 1,970 bytes |
コンパイル時間 | 324 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 178,596 KB |
最終ジャッジ日時 | 2024-11-23 10:09:02 |
合計ジャッジ時間 | 60,342 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
class UnionFindUndo: def __init__(self, n): self.parent = [-1] * n self.history = [] def root(self, x): if self.parent[x] < 0: return x else: return self.root(self.parent[x]) def merge(self, x, y): x = self.root(x) y = self.root(y) self.history.append((x, self.parent[x])) self.history.append((y, self.parent[y])) if x == y: return False if self.parent[x] > self.parent[y]: x, y = y, x self.parent[x] += self.parent[y] self.parent[y] = x return True def undo(self): if not self.history: return False for _ in range(2): x, par_x = self.history.pop() self.parent[x] = par_x return True def same(self, x, y): return self.root(x) == self.root(y) def size(self, x): return -self.parent[self.root(x)] n, q = map(int, input().split()) queries = [list(map(int, input().split())) for _ in range(q)] MOD = 998244353 uf = UnionFindUndo(n + n) ptn = pow(2, n, MOD) inv2 = pow(2, MOD - 2, MOD) for query in queries: if query[0] == 1: _, u, v = query u -= 1 v -= 1 if not uf.same(u, v): uf.merge(u, v) uf.merge(u + n, v + n) ptn *= inv2 ptn %= MOD if uf.same(u, u + n): ptn = 0 if uf.same(v, v + n): ptn = 0 if query[0] == 2: _, u, v = query u -= 1 v -= 1 if not uf.same(u + n, v): uf.merge(u + n, v) uf.merge(u, v + n) ptn *= inv2 ptn %= MOD if uf.same(u, u + n): ptn = 0 if uf.same(v, v + n): ptn = 0 if query[0] == 3: while True: res = uf.undo() if not res: break ptn = pow(2, n, MOD) print(ptn)