結果

問題 No.2291 Union Find Estimate
ユーザー sepa38sepa38
提出日時 2023-05-05 21:56:32
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
WA  
実行時間 -
コード長 1,421 bytes
コンパイル時間 553 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 22,400 KB
最終ジャッジ日時 2024-05-02 16:11:12
合計ジャッジ時間 10,283 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
11,136 KB
testcase_01 AC 26 ms
11,008 KB
testcase_02 AC 1,156 ms
11,008 KB
testcase_03 AC 1,417 ms
22,400 KB
testcase_04 AC 346 ms
11,008 KB
testcase_05 AC 352 ms
11,008 KB
testcase_06 AC 202 ms
10,880 KB
testcase_07 AC 130 ms
10,880 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます

ソースコード

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