結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:52:03 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 161 ms / 2,000 ms |
コード長 | 2,726 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 81,884 KB |
実行使用メモリ | 93,032 KB |
最終ジャッジ日時 | 2025-03-20 18:52:52 |
合計ジャッジ時間 | 2,742 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
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()