結果

問題 No.2494 Sum within Components
ユーザー t9unkubjt9unkubj
提出日時 2023-10-06 21:37:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 8,501 bytes
コンパイル時間 4,112 ms
コンパイル使用メモリ 241,896 KB
実行使用メモリ 14,776 KB
最終ジャッジ日時 2023-10-06 21:37:20
合計ジャッジ時間 5,687 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 10 ms
4,380 KB
testcase_11 AC 5 ms
4,376 KB
testcase_12 AC 8 ms
4,376 KB
testcase_13 AC 7 ms
4,376 KB
testcase_14 AC 56 ms
5,424 KB
testcase_15 AC 50 ms
4,472 KB
testcase_16 AC 64 ms
9,176 KB
testcase_17 AC 107 ms
14,776 KB
testcase_18 AC 105 ms
14,416 KB
testcase_19 AC 92 ms
8,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 insert
using 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;
}
//mod
long 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
0