結果
問題 | No.2494 Sum within Components |
ユーザー |
|
提出日時 | 2023-10-12 18:13:49 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 183 ms / 2,000 ms |
コード長 | 2,453 bytes |
コンパイル時間 | 881 ms |
コンパイル使用メモリ | 124,032 KB |
実行使用メモリ | 7,040 KB |
最終ジャッジ日時 | 2024-09-14 16:42:35 |
合計ジャッジ時間 | 3,403 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <iostream>#include <stdio.h>#include <vector>using namespace std;using i64 = long long;#define yn(pope) (pope ? "Yes" : "No")#define rep(i, n, m) for (int i = (n); i < (m); i++)#define rrep(i, n, m) for (int i = (n); i > m; i--)#define IINF (1 << 30)#define INF (1ll << 60)#define all(v) v.begin(), v.end()struct DSU {public :vector<int> T;DSU(int N) {T.resize(N, -1);}int root(int a) {if (T[a] < 0) {return a;} else {return T[a] = root(T[a]);}}void unite(int a, int b) {int ra = root(a);int rb = root(b);if (ra == rb) { return; }T[rb] += T[ra];T[ra] = rb;}bool same(int a, int b) {return root(a) == root(b);}int size(int a) {return -T[root(a)];}};i64 mod = 998244353ll;struct mint {i64 x;mint(i64 x = 0):x(x % mod) {}mint& operator+=(const mint a) {x = (x + a.x) % mod;return *this;}mint& operator-=(const mint a) {x = (x - a.x + mod) % mod;return *this;}mint& operator*=(const mint a) {x = (x * a.x) % mod;return *this;}mint& operator/=(const mint a) {x = (x * a.inv().x) % mod;return *this;}mint operator+(const mint a) const {mint res(*this); res.x = (res.x + a.x) % mod;return res;}mint operator-(const mint a) const {mint res(*this); res.x = (res.x - a.x + mod) % mod;return res;}mint operator*(const mint a) const {mint res(*this); res.x = (res.x * a.x) % mod;return res;}mint operator/(const mint a) const {mint res(*this); res.x = (res.x * a.inv().x) % mod;return res;}mint pow(i64 pow) const {mint res = 1, base = x;while (pow) {if (pow & 1) {res *= base;}base *= base;pow >>= 1;}return res;}mint inv() const {return pow(mod - 2); // This is only valid when mod is prime.}};istream& operator>>(istream& is, mint& a) { return is >> a.x;}ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}int main() {int N, M; cin >> N >> M;vector<mint> A(N);for (mint &x : A) { cin >> x; }DSU dsu(N);vector<mint> sum(N);rep(i, 0, M) {int u, v; cin >> u >> v; u--, v--;dsu.unite(u, v);}rep(i, 0, N) {sum[dsu.root(i)] += A[i];}mint ans = 1;rep(i, 0, N) {ans *= sum[dsu.root(i)];}cout << ans << endl;return 0;}