結果

問題 No.2291 Union Find Estimate
コンテスト
ユーザー sepa38
提出日時 2023-05-05 21:56:32
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,421 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-11-23 07:24:20
合計ジャッジ時間 11,540 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(500000)
class UF:
  def __init__(self, n):
    self.root = [i for i in range(n)]
    self.subt = [1] * n

  def find(self, x):
    if self.root[x] == x:
      return x
    else:
      self.root[x] = self.find(self.root[x])
      return self.root[x]

  def union(self, x, y):
    x, y = self.find(x), self.find(y)
    x, y = min(x, y), max(x, y)
    if x != y:
      self.subt[x] += self.subt[y]
    self.root[y] = x

  def size(self, x):
    return self.subt[self.find(x)]


w, h = map(int, input().split())
uf = UF(w)
mod = 998244353
ans = pow(10, w, mod)
flg = [0] * w
for i in range(h):
  q = input()
  root = dict()
  for j in range(w):
    if "0" <= q[j] <= "9":
      if flg[uf.find(j)]:
        if flg[uf.find(j)] != q[j]:
          ans = 0
        continue
      flg[uf.find(j)] = q[j]
      ans *= pow(10, mod-2, mod)
      ans %= mod
    elif "a" <= q[j] <= "z":
      if q[j] not in root:
        root[q[j]] = j
      else:
        if flg[uf.find(root[q[j]])] and flg[uf.find(j)] and flg[uf.find(root[q[j]])] != flg[uf.find(j)]:
          ans = 0
        if uf.find(root[q[j]]) != uf.find(j) and not flg[uf.find(root[q[j]])] or not flg[uf.find(j)]:
          ans *= pow(10, mod-2, mod)
          ans %= mod
        uf.union(root[q[j]], j)
        if flg[j]:
          flg[uf.find(j)] = flg[j]
        if flg[root[q[j]]]:
          flg[uf.find(j)] = flg[root[q[j]]]
  print(ans)
0