結果
問題 |
No.2494 Sum within Components
|
ユーザー |
|
提出日時 | 2024-02-03 14:55:45 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 1,248 bytes |
コンパイル時間 | 23,867 ms |
コンパイル使用メモリ | 358,356 KB |
最終ジャッジ日時 | 2025-02-19 01:10:23 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; using ll=long long; using ld=long double; using T=tuple<ld,ll,ll>; void IO(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); } int main(){ IO(); ll n,m; cin>>n>>m; vector<ll> a(n); for(ll i=0;i<n;i++){ cin>>a[i]; } vector<vector<ll>> G(n); for(ll i=0;i<m;i++){ ll u,v; cin>>u>>v; u--; v--; G[u].push_back(v); G[v].push_back(u); } vector<bool> seen(n,false); queue<ll> que; vector<vector<ll>> v; ll idx=0; for(ll i=0;i<n;i++){ if(!seen[i]){ seen[i]=true; que.push(i); v.resize(idx+1); while(que.size()){ ll q=que.front(); que.pop(); v[idx].push_back(q); for(ll u:G[q]){ if(!seen[u]){ seen[u]=true; que.push(u); } } } idx++; } } ll mod=998244353; ll ans=1; for(ll i=0;i<idx;i++){ ll tmp=0; ll sz=v[i].size(); for(ll j:v[i]){ tmp+=a[j]; tmp%=mod; } for(ll j=0;j<sz;j++){ ans*=tmp; ans%=mod; } } cout<<ans<<endl; }