結果
問題 | No.2494 Sum within Components |
ユーザー |
![]() |
提出日時 | 2023-11-12 17:19:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 2,482 bytes |
コンパイル時間 | 1,970 ms |
コンパイル使用メモリ | 170,524 KB |
実行使用メモリ | 9,472 KB |
最終ジャッジ日時 | 2024-09-26 03:02:27 |
合計ジャッジ時間 | 3,227 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll =long long;#define all(v) v.begin(),v.end()#define rep(i,a,b) for(int i=a;i<b;i++)#define rrep(i,a,b) for(int i=a;i>=b;i--)ll INF=2e18;const int mod = 998244353;class mint {long long x;public:mint(long long x=0) : x((x%mod+mod)%mod) {}mint operator-() const {return mint(-x);}mint& operator+=(const mint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint& a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint& a) const {mint res(*this);return res+=a;}mint operator-(const mint& a) const {mint res(*this);return res-=a;}mint operator*(const mint& a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint& a) {return (*this) *= a.inv();}mint operator/(const mint& a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& m){os << m.x;return os;}};struct UnionFind {vector<ll> par;vector<ll> r;void init(ll n) {par=vector<ll> (n);r=vector<ll> (n);for(ll i=0;i<n;i++) {par[i]=i;r[i]=0LL;}}ll find(ll x) {if(par[x]==x) {return x;}return par[x]=find(par[x]);}void unite(ll x,ll y) {x=find(x);y=find(y);if(x==y) {return;}if(r[x]<r[y]) {par[x]=y;}else {par[y]=x;if(r[x]==r[y]) {r[x]++;}}}bool same(ll x,ll y) {return find(x)==find(y);}};int main() {ios::sync_with_stdio(false);cin.tie(0);ll N,M;cin>>N>>M;vector<ll> A(N);for(ll i=0;i<N;i++) cin>>A[i];UnionFind uni;uni.init(N);for(ll i=0;i<M;i++) {ll U,V;cin>>U>>V;U--;V--;uni.unite(U,V);}vector<ll> sum(N);for(ll i=0;i<N;i++) {ll k=uni.find(i);sum[k]+=A[i];}mint ans=1;for(ll i=0;i<N;i++) {ll k=uni.find(i);ans*=sum[k];}cout<<ans<<endl;}