結果
問題 | No.2494 Sum within Components |
ユーザー | inkyaman |
提出日時 | 2024-03-24 16:46:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 227 ms / 2,000 ms |
コード長 | 1,367 bytes |
コンパイル時間 | 1,228 ms |
コンパイル使用メモリ | 126,884 KB |
実行使用メモリ | 15,936 KB |
最終ジャッジ日時 | 2024-03-24 16:46:58 |
合計ジャッジ時間 | 3,869 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
8,512 KB |
testcase_01 | AC | 3 ms
8,512 KB |
testcase_02 | AC | 3 ms
8,512 KB |
testcase_03 | AC | 3 ms
8,512 KB |
testcase_04 | AC | 3 ms
8,512 KB |
testcase_05 | AC | 3 ms
8,512 KB |
testcase_06 | AC | 3 ms
8,512 KB |
testcase_07 | AC | 3 ms
8,512 KB |
testcase_08 | AC | 3 ms
8,512 KB |
testcase_09 | AC | 14 ms
8,896 KB |
testcase_10 | AC | 17 ms
9,004 KB |
testcase_11 | AC | 8 ms
8,640 KB |
testcase_12 | AC | 25 ms
9,280 KB |
testcase_13 | AC | 16 ms
9,024 KB |
testcase_14 | AC | 183 ms
14,400 KB |
testcase_15 | AC | 189 ms
13,760 KB |
testcase_16 | AC | 94 ms
11,200 KB |
testcase_17 | AC | 105 ms
10,432 KB |
testcase_18 | AC | 115 ms
11,072 KB |
testcase_19 | AC | 227 ms
15,936 KB |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <string> #include <algorithm> #include <vector> #include <queue> #include <math.h> #include <cmath> #include <stack> #include <map> #include <set> #include <numeric> #include <iomanip> #include <climits> #include <functional> #include <cassert> #include <tuple> using namespace std; using ll = long long; int N,M; vector<int> G[202020]; int A[202020]; ll mod = 998244353; int main() { cin >> N >> M; for(int i = 1; i <= N; ++i) cin >> A[i]; for(int i = 0; i < M; ++i) { int u,v; cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } ll ans = 1; vector<bool> vis(N+1); vector<ll> S(N+1); for(int i = 1; i <= N; ++i) { if(vis[i]) continue; ll sum = 0; vis[i] = true; queue<int> q; vector<int> route; q.push(i); route.push_back(i); while(!q.empty()) { int v = q.front(); q.pop(); sum += A[v]; sum %= mod; for(int ne : G[v]) { if(vis[ne]) continue; vis[ne] = true; q.push(ne); route.push_back(ne); } } for(int v : route) S[v] = sum; } for(int i = 1; i <= N; ++i) { ans *= S[i]; ans %= mod; } cout << ans << endl; }