結果
問題 | No.2494 Sum within Components |
ユーザー |
|
提出日時 | 2023-10-06 21:52:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 5,588 bytes |
コンパイル時間 | 2,926 ms |
コンパイル使用メモリ | 249,852 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2024-07-26 16:02:07 |
合計ジャッジ時間 | 4,947 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define rep2(i, s, n) for (ll i = s; i <= (ll)(n); i++)#define rep3(i, s, n, d) for (ll i = s; i <= (ll)(n); i += d)#define rep4(i, s, n, d) for (ll i = s; i >= (ll)(n); i += d)typedef long long ll;typedef long double ld;typedef vector<int> vi;typedef vector<vi> vvi;typedef vector<vvi> vvvi;typedef vector<vvvi> vvvvi;typedef vector<string> vs;typedef vector<vs> vvs;typedef vector<vvs> vvvs;typedef vector<char> vc;typedef vector<vc> vvc;typedef vector<vvc> vvvc;typedef vector<ll> vll;typedef vector<vll> vvll;typedef vector<vvll> vvvll;typedef vector<vvvll> vvvvll;typedef vector<vvvvll> vvvvvll;typedef vector<double> vd;typedef vector<vd> vvd;typedef vector<vvd> vvvd;typedef vector<ld> vld;typedef vector<vld> vvld;typedef vector<vvld> vvvld;typedef vector<bool> vb;typedef vector<vd> vvb;typedef vector<vvd> vvvb;typedef vector<pair<int, int>> vpi;typedef vector<pair<ll, ll>> vpll;typedef priority_queue<int, vector<int>, greater<int>> pqi;typedef priority_queue<vi, vector<vi>, greater<vi>> pqvi;typedef priority_queue<ll, vector<ll>, greater<ll>> pqll;typedef priority_queue<vll, vector<vll>, greater<vll>> pqvll;typedef priority_queue<int, vector<int>, less<int>> rpqi;typedef priority_queue<vi, vector<vi>, less<vi>> rpqvi;typedef pair<int, int> P;#define yes(ans) if(ans)cout << "yes"<< endl; else cout << "no" << endl#define Yes(ans) if(ans)cout << "Yes"<< endl; else cout << "No" << endl#define YES(ans) if(ans)cout << "YES"<< endl ;else cout << "NO" << endl#define printv(vec) rep(i, vec.size()) cout << vec[i] << ' ';#define printvv(vec) rep(i, vec.size()) {rep(j, vec[i].size()) cout << vec[i][j] << ' '; cout << endl;};#define printvvv(vec) rep(i, vec.size()) { rep(j, vec[i].size()) { rep(k, vec[i][j].size()) cout << vec[i][j][k] << ' '; cout << " "; }cout << endl;};#define all1(x) x.begin(),x.end()#define all2(x) x.rbegin(), x.rend()#define so(x) sort(all1(x))#define re(x) reverse(all1(x))#define rso(x) sort(all2(x))#define vco(x, a) count(all1(x), a)#define per(x) next_permutation(all1(x))#define iINF 2147483647#define llINF 9223372036854775807#define mod 998244353#define mod2 1000000007template<int MOD> struct Fp {long long val;constexpr Fp(long long v = 0) noexcept : val(v% MOD) {if (val < 0) val += MOD;}constexpr int getmod() { return MOD; }constexpr Fp operator - () const noexcept {return val ? MOD - val : 0;}constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }constexpr Fp& operator += (const Fp& r) noexcept {val += r.val;if (val >= MOD) val -= MOD;return *this;}constexpr Fp& operator -= (const Fp& r) noexcept {val -= r.val;if (val < 0) val += MOD;return *this;}constexpr Fp& operator *= (const Fp& r) noexcept {val = val * r.val % MOD;return *this;}constexpr Fp& operator /= (const Fp& r) noexcept {long long a = r.val, b = MOD, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}val = val * u % MOD;if (val < 0) val += MOD;return *this;}constexpr bool operator == (const Fp& r) const noexcept {return this->val == r.val;}constexpr bool operator != (const Fp& r) const noexcept {return this->val != r.val;}friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {return os << x.val;}friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {if (n == 0) return 1;auto t = modpow(a, n / 2);t = t * t;if (n & 1) t = t * a;return t;}};using mint = Fp<mod>;typedef vector<mint> vm;typedef vector<vm> vvm;typedef vector<vvm> vvvm;typedef vector<vvvm> vvvvm;struct UnionFind {vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化for (int i = 0; i < N; i++) par[i] = i;}int root(int x) { // データxが属する木の根を再帰で得る:root(x) = {xの木の根}if (par[x] == x) return x;return par[x] = root(par[x]);}void unite(int x, int y) { // xとyの木を併合int rx = root(x); //xの根をrxint ry = root(y); //yの根をryif (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのままpar[rx] = ry; //xとyの根が同じでない(=同じ木にない)時:xの根rxをyの根ryにつける}bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返すint rx = root(x);int ry = root(y);return rx == ry;}};int main() {int n, m; cin >> n >> m;vi num(n); rep(i, n) cin >> num[i];UnionFind tree(n);rep(i, m) {int a, b; cin >> a >> b;a--, b--;tree.unite(a, b);}vm sum(n);rep(i, n) sum[tree.root(i)] += num[i];mint ans = 1;rep(i, n) ans *= sum[tree.root(i)];cout << ans << endl;}