結果
問題 |
No.2494 Sum within Components
|
ユーザー |
![]() |
提出日時 | 2023-10-06 22:05:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 449 ms / 2,000 ms |
コード長 | 1,524 bytes |
コンパイル時間 | 503 ms |
コンパイル使用メモリ | 81,968 KB |
実行使用メモリ | 150,664 KB |
最終ジャッジ日時 | 2024-07-26 16:10:26 |
合計ジャッジ時間 | 4,329 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
N,M = map(int,input().split()) A = [-1] + list(map(int,input().split())) mod = 998244353 G = [] for i in range(N+1): G.append([]) for i in range(M): U,V = map(int,input().split()) G[U].append(V) G[V].append(U) from collections import deque def renketu_seibunsuu(): number_of_renketu = 0 #連結成分数 number_of_visited = 0 #訪問済み頂点 renketu_dict = {} #最後に関数が返す辞書 visited = [False]*(N+1) edge = 0 for ii in range(10_000_000): #連結成分数が1000万を超えそうなときは要調整 QQ = deque() renketu_dict[ii] = [] for i in range(edge+1,len(visited)): if i == 0: continue if visited[i] == False: QQ.append(i) visited[i] = True number_of_visited+=1 renketu_dict[ii].append(i) edge = i break while len(QQ)>0: tmp = QQ.popleft() for j in G[tmp]: if visited[j] == False: visited[j] = True QQ.append(j) number_of_visited+=1 renketu_dict[ii].append(j) if number_of_visited >= N: break return renketu_dict ren_seibun = renketu_seibunsuu() ans = 1 for ind,nex in ren_seibun.items(): tmp = 0 for ii,vv in enumerate(nex): tmp += A[vv] ans *= pow(tmp,len(nex),mod) ans %= mod print(ans%mod)