結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
|
提出日時 | 2025-01-26 00:26:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 480 ms / 2,000 ms |
コード長 | 4,080 bytes |
コンパイル時間 | 344 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 210,028 KB |
最終ジャッジ日時 | 2025-01-26 00:26:22 |
合計ジャッジ時間 | 4,131 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
# https://yukicoder.me/problems/no/132 class UnionFind: """ UnionFindの基本的な処理を実装したクラス """ def __init__(self, size): self.root = [i for i in range(size)] self.size = [1] * size self.root_values = [-1] * size def get_root(self, v): if v == self.root[v]: return v else: old_root = self.root[v] new_root = self.get_root(old_root) self.root[v] = new_root return new_root def merge(self, u, v): root_u = self.get_root(u) root_v = self.get_root(v) if root_u == root_v: return False, True if self.root_values[root_u] == self.root_values[root_v]: new_root_value = self.root_values[root_u] elif self.root_values[root_u] == -1 and self.root_values[root_v] != -1: new_root_value = self.root_values[root_v] elif self.root_values[root_u] != -1 and self.root_values[root_v] == -1: new_root_value = self.root_values[root_u] else: return False, False if self.size[root_u] >= self.size[root_v]: self.size[root_u] += self.size[root_v] self.root[root_v] = root_u self.root[v] = root_u self.root_values[root_u] = new_root_value else: self.size[root_v] += self.size[root_u] self.root[root_u] = root_v self.root[u] = root_v self.root_values[root_v] = new_root_value return True, True MOD = 998244353 def main(): W, H = map(int, input().split()) Q = [] for _ in range(H): Q.append(input()) alphas = {chr(i + ord("a")) for i in range(26)} uf = UnionFind(W + 26 * H) collapse = False answer = pow(10, W, MOD) root_map = {i: 10 for i in range(W)} for index, q_word in enumerate(Q): if collapse: print(0) continue for i in range(W): if q_word[i].isdigit(): v = int(q_word[i]) root_i = uf.get_root(i) if uf.root_values[root_i] == -1: uf.root_values[root_i] = v root_map[root_i] = 1 answer *= pow(10, MOD - 2, MOD) answer %= MOD elif uf.root_values[root_i] != v: collapse = True break elif q_word[i] in alphas: u = i v = W + 26 * index + (ord(q_word[i]) - ord("a")) root_u = uf.get_root(u) root_v = uf.get_root(v) merged, res = uf.merge(u, v) if not res: collapse = True break else: if merged: new_root = uf.get_root(u) if root_u in root_map: x_u = root_map[root_u] del root_map[root_u] answer *= pow(x_u, MOD -2, MOD) answer %= MOD # print(f"root_u = {root_u}, x_u = {x_u}") if root_v in root_map: x_v = root_map[root_v] del root_map[root_v] answer *= pow(x_v, MOD -2, MOD) answer %= MOD # print(f"root_v = {root_v}, x_u = {x_u}") if uf.root_values[new_root] == -1: # print(f"new_root = {new_root}, value = 10") root_map[new_root] = 10 answer *= 10 answer %= MOD else: # print(f"new_root = {new_root}, value = 1") root_map[new_root] = 1 if collapse: print(0) else: print(answer) if __name__ == "__main__": main()