結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
![]() |
提出日時 | 2023-05-05 23:20:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 122 ms / 2,000 ms |
コード長 | 1,612 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 76,672 KB |
最終ジャッジ日時 | 2024-11-23 12:16:56 |
合計ジャッジ時間 | 3,118 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sys input = sys.stdin.readline MOD=998244353 W,H=map(int,input().split()) class UnionFind: def __init__(self, n:int): self.n = n self.parents = [-1] * n def find(self, x:int): if self.parents[x] < 0: return x else: self.parents[x] = self.find(self.parents[x]) return self.parents[x] def union(self, x:int, y:int): x = self.find(x) y = self.find(y) if x == y: return if self.parents[x] > self.parents[y]: x, y = y, x if y<10: x,y=y,x self.parents[x] += self.parents[y] self.parents[y] = x def size(self, x:int): return -self.parents[self.find(x)] def same(self, x:int, y:int): return self.find(x) == self.find(y) uf = UnionFind(10+W) ans = pow(10, W, MOD) div10 = pow(10, MOD-2, MOD) for _ in range(H): Q=input().strip() check = {} for i,s in enumerate(Q,start=10): if s=="?":continue if "a"<=s<="z": if s in check: if uf.same(check[s], i): continue ca=uf.find(check[s]) ci=uf.find(i) if ca<10 and ci<10: ans=0 uf.union(check[s], i) ans = ans * div10 % MOD else: check[s] = i else: root = uf.find(i) s = int(s) if root < 10 and root != s: ans=0 if root != s: uf.union(s, i) ans = ans * div10 % MOD print(ans)