結果
問題 |
No.2291 Union Find Estimate
|
ユーザー |
![]() |
提出日時 | 2023-05-06 01:51:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 245 ms / 2,000 ms |
コード長 | 1,992 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 82,688 KB |
実行使用メモリ | 94,080 KB |
最終ジャッジ日時 | 2024-11-23 14:10:19 |
合計ジャッジ時間 | 3,775 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import sys input = sys.stdin.readline N,Q=map(int,input().split()) mod=998244353 # UnionFind Group = [i for i in range(N)] # グループ分け Nodes = [1]*(N) # 各グループのノードの数 def find(x): while Group[x] != x: x=Group[x] return x def Union(x,y): if find(x) != find(y): if Nodes[find(x)] < Nodes[find(y)]: Nodes[find(y)] += Nodes[find(x)] Nodes[find(x)] = 0 Group[find(x)] = find(y) else: Nodes[find(x)] += Nodes[find(y)] Nodes[find(y)] = 0 Group[find(y)] = find(x) ANS=[-1]*N zeroflag=0 for tests in range(Q): S=input().strip() LIST=[[] for i in range(26)] for j in range(len(S)): if 97<=ord(S[j])<=122: LIST[ord(S[j])-97].append(j) if 48<=ord(S[j])<=57: if ANS[find(j)]!=-1 and ANS[find(j)]!=int(S[j]): zeroflag=1 ANS[j]=int(S[j]) ANS[find(j)]=int(S[j]) #print(zeroflag,ANS,"!") for j in range(26): if LIST[j]!=[]: now=-1 for x in LIST[j]: if ANS[x]!=-1: now=ANS[x] #print("?",x,now) for l in LIST[j]: if l!=x and now!=-1 and ANS[find(l)]!=-1 and ANS[find(l)]!=now: zeroflag=1 else: Union(x,l) if now!=-1: ANS[find(l)]=now for j in range(len(S)): if 48<=ord(S[j])<=57: if ANS[find(j)]!=-1 and ANS[find(j)]!=int(S[j]): zeroflag=1 ANS[j]=int(S[j]) ANS[find(j)]=int(S[j]) #print([find(j) for j in range(N)],LIST,ANS,zeroflag) if zeroflag==1: print(0) else: score=0 for j in range(N): if find(j)==j and ANS[j]==-1: score+=1 print(pow(10,score,mod))