結果
問題 | No.2494 Sum within Components |
ユーザー |
|
提出日時 | 2023-10-06 21:30:10 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 406 ms / 2,000 ms |
コード長 | 1,078 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 119,840 KB |
最終ジャッジ日時 | 2024-07-26 15:46:19 |
合計ジャッジ時間 | 3,561 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
class UnionFind():def __init__(self,size):self.uf=[[-1,0,A[i]] for i in range(size)]def unite(self,fir,sec):one=self.root(fir)two=self.root(sec)if one!=two:if self.uf[one][1]>self.uf[two][1]:one,two=two,oneself.uf[one][0]=twoself.uf[two][2]+=self.uf[one][2]if self.uf[one][1]==self.uf[two][1]:self.uf[two][1]+=1def same(self,fir,sec):return self.root(fir)==self.root(sec)def root(self,node):pos=nodechange=[]while self.uf[pos][0]!=-1:change.append(pos)pos=self.uf[pos][0]for i in change:self.uf[i][0]=posreturn posdef size(self,node):return self.uf[self.root(node)][2]N,M=map(int,input().split())A=list(map(int,input().split()))union=UnionFind(N)for i in range(M):A,B=map(int,input().split())union.unite(A-1,B-1)ans=1for i in range(N):ans*=union.size(i)ans%=998244353print(ans)