結果

問題 No.2291 Union Find Estimate
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:21:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 143 ms / 2,000 ms
コード長 2,726 bytes
コンパイル時間 187 ms
コンパイル使用メモリ 82,040 KB
実行使用メモリ 92,752 KB
最終ジャッジ日時 2025-03-20 21:22:41
合計ジャッジ時間 2,775 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict
MOD = 998244353

def main():
    sys.setrecursionlimit(1 << 25)
    W, H = map(int, stdin.readline().split())
    queries = [stdin.readline().strip() for _ in range(H)]
    parent = list(range(W))
    digit = [None] * W
    count_free = W
    possible = True

    def find(u):
        while parent[u] != u:
            parent[u] = parent[parent[u]]
            u = parent[u]
        return u

    for query in queries:
        if not possible:
            print(0)
            continue

        groups = defaultdict(list)
        for j in range(W):
            c = query[j]
            if 'a' <= c <= 'z':
                groups[c].append(j)

        for c in groups:
            group = groups[c]
            if len(group) < 2:
                continue
            first = group[0]
            for j in group[1:]:
                root_first = find(first)
                root_j = find(j)
                if root_first == root_j:
                    continue
                d_root_first = digit[root_first]
                d_root_j = digit[root_j]

                if d_root_first is not None and d_root_j is not None:
                    if d_root_first != d_root_j:
                        possible = False
                        break
                if not possible:
                    break

                if d_root_first is not None:
                    parent[root_j] = root_first
                    if d_root_j is None:
                        count_free -= 1
                elif d_root_j is not None:
                    parent[root_first] = root_j
                    if d_root_first is None:
                        count_free -= 1
                else:
                    parent[root_j] = root_first
                    count_free -= 1

                if d_root_first is None and d_root_j is None:
                    pass
                elif d_root_first is None:
                    pass
                elif d_root_j is None:
                    pass

            if not possible:
                break
        if not possible:
            pass
        else:
            for j in range(W):
                c = query[j]
                if not c.isdigit():
                    continue
                d = int(c)
                root = find(j)
                if digit[root] is None:
                    digit[root] = d
                    count_free -= 1
                elif digit[root] != d:
                    possible = False
                if not possible:
                    break

        if not possible:
            print(0)
        else:
            print(pow(10, count_free, MOD))

if __name__ == "__main__":
    main()
0