結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 t9unkubj
|
| 提出日時 | 2023-10-06 21:37:14 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 93 ms / 2,000 ms |
| コード長 | 8,501 bytes |
| コンパイル時間 | 4,443 ms |
| コンパイル使用メモリ | 245,720 KB |
| 実行使用メモリ | 14,976 KB |
| 最終ジャッジ日時 | 2024-07-26 15:51:46 |
| 合計ジャッジ時間 | 5,025 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
#ifndef INCLUDED_MAIN#define INCLUDED_MAIN#include __FILE__#include <atcoder/all>using namespace atcoder;void solve();void s() {int t = 1;rep(i, t)solve();}using mint = modint998244353;void solve() {int n, m;cin >> n >> m;vl a(n);in(a);dsu U(n);rep(i, m) {int u, v;cin >> u >> v;u--; v--;U.merge(u, v);}map<int, mint> ma;rep(i, n) {ma[U.leader(i)] += a[i];}mint ans = 1;rep(i, n) {ans *= ma[U.leader(i)];}cout << ans.val() << endl;}int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(20);s();return 0;}#else // INCLUDED_MAIN#include <bits/stdc++.h>#pragma GCC optimize("O2")using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)#define drep(i,n) for(ll i=(long long)n;i>=0;i--)#define DREP(i,n,m) for(int i=n;i>=m;i--)#define REP(i,n,m) for(int i=n;i<(m);i++)#define fi first#define se second#define pb push_back#define mp make_pair#define ti tuple<int,int,int>#define tl tuple<ll,ll,ll>#define mt make_tuple#define all(o) (o).begin(), (o).end()#define YESNO(bool) if(bool){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}#define yesno(bool) if(bool){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}#define yn(bool) YesNo(bool)#define dame cout<<-1<<endl;#define bye return;#define bye0 return 0;#define vec vector#define vvi vector<vector<int>>#define vvl vector<vector<ll>>#define vvvl vector<vvl>#define vvvvl vector<vvvl>#define vi vector<int>#define vp vector<pii>#define vpl vector<pll>#define ge(x,i) get<i>(x)#define vl vector<ll>#define vs vector<string>#define vvvi vector<vvi>#define vb vector<bool>#define vvb vector<vector<bool>>#define vvvb vec<vvb>#define vs vector<string>#define vvs vector<vs>#define vd vector<double>#define vvd vector<vd>#define vld vector<ld>#define vvld vector<vld>#define pque priority_queue#define smpq(n) priority_queue<n,vector<n>,greater<n>>#define bipq(n) priority_queue<n, vector<n>,less<n>>#define sz(o) o.size()#define piii pair<int,pair<int,int>>#define ednl endl#define denl endl#define Endl endl#define Yes cout<<"Yes"<<endl;#define No cout << "No"<<endl;#define OUT(n) cout<<n<<endl;#define fore(x,y) for(auto&x:y)#define nep next_permutation#define is insertusing ll = long long;using ull = unsigned long long;using pii = pair<int, int>;using pll = pair<ll, ll>;using plll = pair<ll, pll>;using db = double;using ld = long double;template<typename T>using vc = vector<T>;template<typename T>using vvc = vector<vc<T>>;template<typename T>using vvvc = vector<vvc<T>>;template<typename T>using vvvvc = vector<vvvc<T>>;const long double pi = 3.1415926535897932384626433;const int inf = (1LL << 30) - 1;ll INF = (1LL << 62) - 1;const ll mod7 = 1e9 + 7;const ll mod9 = 998244353;template<typename T> inline bool chmax(T& a, T b) { return ((a < b) ? (a = b, true) : (false)); }template<typename T> inline bool chmin(T& a, T b) { return ((a > b) ? (a = b, true) : (false)); }int zero() { return 0; }ll zerol() { return 0l; }int plus(int a, int b) { return a + b; }int mini(int a, int b) { return min(a, b); }ll plusl(ll a, ll b) { return a + b; }ll minl(ll a, ll b) { return min(a, b); }int infi() { return inf; };ll infl() { return INF; }template<typename T>T sum(vector<T>& a) {T ret = 0;rep(i, a.size())ret += a[i];return ret;}template<typename T>void in(vector<T>& a) {for (auto& x : a)cin >> x;}template<typename T>void out(vector<T>& a) {rep(i, a.size()) {if (i)cout << " ";cout << a[i];}cout << endl;}//方向int dx[4] = { -1,0,1,0 };int dy[4] = { 0,1,0,-1 };int sy[8] = { 1,-1,0,1,-1,1,0,-1 };int dx1[6] = { 1,1,1,0,0,-1 };int dy1[6] = { -1,0,1,-1,1,0 };int dx2[6] = { -1,0,1,0,-1,-1 };int dy2[6] = { 1,1,0,-1,-1,0 };vi dx8 = { 1,1,1,0,0,-1,-1,-1 };vi dy8 = { 1,-1,0,1,-1,1,0,-1 };ull POW(ull a, ull b) {ull res = 1;rep(i, b) {res *= a;}return res;}vi kmp(string s) {vi a(s.size());int j = -1;rep(i, s.size()) {while (j >= 0 && s[i] != s[j])j = a[j];j++;a[i + 1] = j;}return a;}struct Unionfind {vector<int> parent, size, mi;Unionfind(int n) : parent(n, -1), size(n, 1), mi(n, INF) {}void init() {rep(i, mi.size())mi[i] = i;}int root(int x) {if (parent[x] == -1) return x;return parent[x] = root(parent[x]);}bool same(int x, int y) {return root(x) == root(y);}int siz(int x) {return size[root(x)];}void unite(int x, int y) {int rootX = root(x);int rootY = root(y);if (rootX == rootY) return;chmin(mi[rootX], mi[rootY]);chmin(mi[rootY], mi[rootX]);if (size[rootX] < size[rootY]) swap(rootX, rootY);parent[rootY] = rootX;size[rootX] += size[rootY];}int m(int x) {return mi[root(x)];}};struct COM {vector<ll> fac, finv, inv;ll MOD = 1;COM(int n, ll mod) {fac.resize(n);finv.resize(n);inv.resize(n);MOD = mod;ll MAX = n;fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++) {fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}ll com(int n,int k) {if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}};vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod) {// 行列乗算int n = a.size();vector<vector<ll>> res(n, vector<ll>(n));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int k = 0; k < n; k++) {res[i][j] += a[i][k] * b[k][j];res[i][j] %= mod;}}}return res;}vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll b, ll mod) {// 行列累乗int n = a.size();vector<vector<ll>> res(n, vector<ll>(n));for (int i = 0; i < n; i++) res[i][i] = 1;while (b) {if (b & 1) res = mat_mul(res, a, mod);a = mat_mul(a, a, mod);b >>= 1;}return res;}//modlong long modpow(long long a, long long b, long long m) {if (a % m == 0)return 0;long long p = 1, q = a;q %= m;if (b < 0)return 0;for (int i = 0; i < 63; i++) {if ((b & (1LL << i)) != 0) {p *= q;p %= m;}q *= q;q %= m;}return p;}bool Find(string a, string b) {if (a.find(b) == string::npos)return false;return true;}ll modinv(ll n, ll mod) {return modpow(n, mod - 2, mod);}ll gcd(ll a, ll b) {if (a % b == 0) {if (b > 0)return b;else return -b;}else {return gcd(b, a % b);}}ll lcm(ll a, ll b) {return a * b / gcd(a, b);}template <typename T>tuple<T, T, T> treediameter(vector<vector<pair<T, T>>>& road, T n, T INF) {queue<T> que;que.push(0);vb seen(n);vector<T> mda(n);mda[0] = 0;seen[0] = true;T b;while (que.size()) {auto p = que.front(); que.pop();for (auto x : road[p]) {if (!seen[x.fi]) {mda[x.fi] = mda[p] + x.se;b = x.fi;que.push(x.fi);seen[x.fi] = true;}}}T f = -INF;rep(i, n) {if (chmax(f, mda[i])) {b = i;}}que.push(b);rep(i, n)seen[i] = false;seen[b] = true;vector<T> mdb(n);mdb[b] = 0;T a;while (que.size()) {auto p = que.front(); que.pop();for (auto x : road[p]) {if (!seen[x.fi]) {mdb[x.fi] = mdb[p] + x.se;que.push(x.fi);seen[x.fi] = true;}}}T g = -INF;rep(i, n) {if (chmax(g, mdb[i])) {a = i;}}return make_tuple(a, b, mdb[a]);}void manhattanmst(vector<pll> points) {}//////////////////#endif