結果
問題 | No.2134 -algebra over Finite Set |
ユーザー |
![]() |
提出日時 | 2022-11-26 00:18:08 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 881 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,636 KB |
実行使用メモリ | 77,644 KB |
最終ジャッジ日時 | 2024-10-02 06:35:18 |
合計ジャッジ時間 | 2,896 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 11 WA * 6 |
ソースコード
class UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnif self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xn,m = map(int,input().split())uf = UnionFind(n)for i in range(m):l = list(map(int,input().split()))v = [0] * nfor j in range(1, l[0]+1):v[l[j] - 1] = 1a = -1b = -1for j in range(n):if v[j] == 1:if a >= 0:uf.union(a, j)a = jelse:if b >= 0:uf.union(b, j)b = jmod = 998244353ans = pow(2, n+1, mod)inv2 = pow(2, mod-2, mod)for i in range(n):if uf.parents[i] < 0:ans *= inv2ans %= modprint(ans)