結果
問題 | No.2293 無向辺 2-SAT |
ユーザー |
![]() |
提出日時 | 2023-05-06 01:06:21 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,156 bytes |
コンパイル時間 | 603 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 117,548 KB |
最終ジャッジ日時 | 2024-11-23 13:46:17 |
合計ジャッジ時間 | 40,725 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 WA * 39 |
ソースコード
import sysinput = sys.stdin.readlineclass UnionFind(object):def __init__(self, n=1):self.par = [i for i in range(n)]self.rank = [0 for _ in range(n)]self.size = [1 for _ in range(n)]self.diff_weight = [0 for _ in range(n)]self.flag = 1def find(self, x):if self.par[x] == x:return xelse:self.par[x] = self.find(self.par[x])self.diff_weight[x] ^= self.diff_weight[self.par[x]]return self.par[x]def union(self, x, y, w):rx = self.find(x)ry = self.find(y)w ^= self.diff_weight[y]^self.diff_weight[x]if rx != ry:if self.rank[rx] < self.rank[ry]:rx, ry = ry, rxif self.rank[rx] == self.rank[ry]:self.rank[rx] += 1self.par[ry] = rxself.size[rx] += self.size[ry]else:if w:self.flag = 0def is_same(self, x, y):return self.find(x) == self.find(y)def get_size(self, x):x = self.find(x)return self.size[x]def diff(self, x, y):return self.diff_weight[self.find(y)]^self.diff_weight[self.find(x)]N, Q = map(int, input().split())mod = 998244353N2 = pow(2, N, mod)ans = N2inv = pow(2, mod - 2, mod)U = UnionFind(N)stack = set()for _ in range(Q):query = list(map(int, input().split()))if query[0] == 1:u, v = query[1:]u, v = u - 1, v - 1stack.add(u)stack.add(v)if not U.is_same(u, v):ans *= invans %= modU.union(u, v, 0)elif query[0] == 2:u, v = query[1:]u, v = u - 1, v - 1stack.add(u)stack.add(v)if not U.is_same(u, v):ans *= invans %= modU.union(u, v, 1)else:ans = N2U.flag = 1for s in stack:U.diff_weight[s] = 0U.par[s] = sU.rank[s] = 0U.size[s] = 1stack = set()if U.flag:print(ans)else:print(0)