結果

問題 No.2291 Union Find Estimate
ユーザー qibqib
提出日時 2023-05-06 04:04:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,076 bytes
コンパイル時間 215 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 95,528 KB
最終ジャッジ日時 2024-11-23 15:28:30
合計ジャッジ時間 3,981 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1 WA * 1
other AC * 16 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

MOD = 998244353
class UnionFind:
def __init__(self, n):
self.node = [-1 for _ in range(n)]
def root(self, v):
if self.node[v] < 0:
return v
st = []
while self.node[v] >= 0:
st.append(v)
v = self.node[v]
for u in st:
self.node[u] = v
return v
def size(self, v):
v = self.root(v)
return (- self.node[v])
def same(self, u, v):
return self.root(u) == self.root(v)
def unite(self, u, v):
ru = self.root(u)
rv = self.root(v)
if ru == rv:
return
du = self.node[ru]
dv = self.node[rv]
if du <= dv:
self.node[rv] = ru
self.node[ru] += dv
else:
self.node[ru] = rv
self.node[rv] += du
w, h = map(int, input().split())
uf = UnionFind(w)
num = [None for _ in range(w)]
flg = True
for _ in range(h):
qi = input()
ans = 1
if not flg:
ans = 0
idx = {}
for j in range(w * ans):
if qi[j] == "?":
continue
elif ord("a") <= ord(qi[j]) <= ord("z"):
if idx.get(qi[j], None) is None:
idx[qi[j]] = j
else:
uf.unite(idx[qi[j]], j)
r = uf.root(j)
none_r = num[r] is None
none_j = num[j] is None
if not none_r and not none_j:
if num[r] != num[j]:
flg = False
ans = 0
break
elif none_r and not none_j:
num[r] = num[j]
elif none_j and not none_r:
num[j] = num[r]
else:
if num[j] is None:
num[j] = int(qi[j])
elif num[j] != int(qi[j]):
flg = False
ans = 0
break
par = {}
for v in range(w * ans):
r = uf.root(v)
none_r = num[r] is None
none_v = num[v] is None
if not none_r and not none_v:
if num[r] != num[v]:
flg = False
ans = 0
break
elif none_r and not none_v:
num[r] = num[v]
elif none_v and not none_r:
num[v] = num[r]
if par.get(r, None) is None:
par[r] = num[r]
for k, v in par.items():
if v is None:
ans = (ans * 10) % MOD
print(ans)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0