結果

問題 No.2291 Union Find Estimate
コンテスト
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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()
0