結果
問題 | No.2291 Union Find Estimate |
ユーザー |
👑 ![]() |
提出日時 | 2023-05-05 21:49:13 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 233 ms / 2,000 ms |
コード長 | 4,653 bytes |
コンパイル時間 | 852 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 92,020 KB |
最終ジャッジ日時 | 2024-11-23 06:55:28 |
合計ジャッジ時間 | 3,943 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
class Coloring_Union_Find():__slots__=("n", "parents", "rank", "data", "merge", "__group_number")def __init__(self, N, merge, unit):""" 0,1,...,N-1 を要素として初期化する.N: 要素数merge: 合成の方法e: 最初の値"""self.n=Nself.parents=[-1]*Nself.data=[unit]*Nself.rank=[0]*Nself.merge=mergeself.__group_number=Ndef find(self, x):""" 要素 x の属している族を調べる.x: 要素"""V=[]while self.parents[x]>=0:V.append(x)x=self.parents[x]for v in V:self.parents[v]=xreturn xdef union(self, x, y):""" 要素 x,y を同一視し, それぞれが持っている族の色を統合する.x,y: 要素"""x=self.find(x)y=self.find(y)if x==y:returnself.__group_number-=1self.data[x]=self.data[y]=self.merge(self.data[x], self.data[y])if self.rank[x]<self.rank[y]:x,y=y,xself.parents[x]+=self.parents[y]self.parents[y]=xif self.rank[x]==self.rank[y]:self.rank[x]+=1def size(self, x):""" 要素 x の属している族の要素の数.x: 要素"""return -self.parents[self.find(x)]def same(self, x, y):""" 要素 x,y は同一視されているか?x,y: 要素"""return self.find(x) == self.find(y)def update(self, x, color):""" 要素 x の属する族の色を color に変更する.x: 要素color: 色"""self.data[self.find(x)]=colordef get(self, x):""" 要素 x の属する属の色を求める.x: 要素"""return self.data[self.find(x)]def members(self, x):""" 要素 x が属している族の要素.※族の要素の個数が欲しいときは size を使うこと!!x: 要素"""root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):""" 族の名前のリスト"""return [i for i,x in enumerate(self.parents) if x < 0]def group_count(self):""" 族の個数"""return self.__group_numberdef all_group_members(self):""" 全ての族の出力"""X={r:[] for r in self.roots()}for k in range(self.n):X[self.find(k)].append(k)return Xdef list(self):return [self.get(x) for x in range(self.n)]def map(self):return {x:self.get(x) for x in self.roots()}def __str__(self):string=[]for x,g in self.all_group_members().items():string.append(" ({}) {}".format(self.get(x), g))return ",".join(string)def __repr__(self):return "Coloring Union Find:"+str(self)def __getitem__(self,index):return self.data[self.find(index)]def __setitem__(self,index,value):self.data[self.find(index)]=value#==================================================def solve():from collections import defaultdictW,H=map(int,input().split())def merge(a,b):if a!=-1:return aelse:return bU=Coloring_Union_Find(W, merge, -1)Mod=998244353TEN=[0]*(W+1); TEN[0]=1for j in range(1,W+1):TEN[j]=(10*TEN[j-1])%Modflag=1Ans=[0]*HS=0for i in range(H):Q=input()data=defaultdict(list)for j in range(W):if "0"<=Q[j]<="9":x=int(Q[j])if U.get(j)!=-1 and U.get(j)!=x:flag=Falseif U.get(j)==-1:S+=1U.update(j,x)elif "a"<=Q[j]<="z":data[Q[j]].append(j)else:passfor a in data:for k in range(len(data[a])-1):p=U.get(data[a][k]); q=U.get(data[a][k+1])if p!=-1 and q!=-1:if p!=q:flag=Falseif p==q and not U.same(data[a][k], data[a][k+1]):S-=1U.union(data[a][k], data[a][k+1])Ans[i]=TEN[U.group_count()-S] if flag else 0return Ans#==================================================import sysinput=sys.stdin.readlinewrite=sys.stdout.writewrite("\n".join(map(str,solve())))