結果

問題 No.2494 Sum within Components
コンテスト
ユーザー mkreem
提出日時 2024-04-15 01:07:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 13,677 bytes
コンパイル時間 2,822 ms
コンパイル使用メモリ 267,864 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-04 08:04:30
合計ジャッジ時間 4,755 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef READ_MAIN
#define READ_MAIN
#include __FILE__

const ll mod = 998244353; using mint = atcoder::modint998244353;
//const ll mod = 1000000007; using mint = atcoder::modint1000000007;

//------------------------------------------------------------------------------------------------------------------
class UnionFind{
public:
    // @param root 各ノードの根を保持（根自身は、「-（根が管轄する集合のノード数）」を保持）
    vector<int> root;

    UnionFind() { }
    UnionFind(int n) : root(n, -1) { }
    void init(int n) { root.assign(n, -1); } // リセット

    // @brief ノードxの根を返す
    int leader(int x){
        if(root[x] < 0) return x; // x自身が根
        else return root[x] = leader(root[x]); // 親を、根に到達するまで再帰的にたぐっていく
    }

    // @brief 同じ集合に属しているかどうかを判定
    bool same(int x, int y){
        return leader(x) == leader(y);
    }

    // @brief 同じ集合にする
    bool merge(int x, int y){
        x = leader(x), y = leader(y);

        if(x == y) return false; // 根が同じなら、既に同じ集合
        if(root[x] > root[y]) swap(x, y); // マージテク
        root[x] += root[y];
        root[y] = x;
        return true;
    }

    // @brief xが属している集合のノード数を返す
    int size(int x){
        return -root[leader(x)];
    }


    // @brief 集合構造の詳細を取得
    vector<vector<int>> groups() {
        // @param member[v] 要素vを根とする集合（根を含む）
        vector<vector<int>> member(root.size()); // root.size() == n
        rep(v, 0, (int)root.size()){
            member[leader(v)].push_back(v);
        }

        // @param res 配列memberの、空の部分を削除したもの
        vector<vector<int>> res;
        rep(v, 0, (int)root.size()){
            if(!member[v].empty()){
                res.push_back(member[v]);
            }
        }
        return res;
    }
};
//------------------------------------------------------------------------------------------------------------------



int main(){
    fast();

    int n, m; cin >> n >> m;
    vector<ll> a(n);
    fore(x, a) cin >> x;
    UnionFind uf(n);
    rep(i, 0, m){
        int u, v; cin >> u >> v;
        u--; v--;
        uf.merge(u, v);
    }

    vector<mint> cnt(n+9);
    rep(v, 0, n){
        int ldr = uf.leader(v);
        cnt[ldr] += a[v];
    }

    mint ans = 1;
    rep(v, 0, n){
        ans *= cnt[uf.leader(v)];
    }

    cout << ans.val() << newl;

}

#else

#include <bits/stdc++.h>
//// data structure
//#include <atcoder/fenwicktree>
//#include <atcoder/segtree>
#include <atcoder/lazysegtree>
//#include <atcoder/string>
//// math
#include <atcoder/math>
//#include <atcoder/convolution>
#include <atcoder/modint>
//// graph
//#include <atcoder/dsu>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/scc>
//#include <atcoder/twosat>

void fast(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout << std::setprecision(15);
}
/*
バグが見つからないとき(RE)...
入力の仕方でミスっている可能性大
セグフォなら、配列の要素参照を、添字演算子から.at()に変えてみる
怪しい場所をコメントアウトしてコンパイルしてみる
*/
// g++ -ggdb -O2 hoge.cpp -I ~/.pml/ac-library -o zzz
/*
メイン関数内に記述すること
std::ifstream in("testcase/hoge"); std::cin.rdbuf(in.rdbuf());
*/

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define debug(x) cout << #x << " = " << (x) << newl;
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define shift(i) (1LL<<(i))
#define bit(n, k) ((n>>k) & 1) // nのkビット目
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define fore(i, a) for(auto &i : a)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define vv(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define vvv(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define vvvv(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define vvvvv(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using pq = std::priority_queue<T>;
template <typename T>
using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// @brief シフト演算子を、__int128_t型用にオーバーロード
std::ostream& operator<<(std::ostream& os, __int128_t value){
    if(value == 0) return os << 0;

    static char buffer[128];
    if(value < 0){
        os << '-';
        value = -value;
    }
    int itr = 0;
    while(value > 0){
        buffer[itr++] = value%10 + '0';
        value /= 10;
    }
    std::reverse(buffer, buffer + itr);
    buffer[itr] = 0;
    return os << buffer;
}
// @brief string型の10進非負整数を、__128_t型に変換する
__int128_t parse(const std::string& s){
    __int128_t res = 0;
    for(int i = 0; i < s.length(); i++){
        res = 10*res + (s[i]-'0');
    }
    return res;
}
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if(a < b){ a = b; return 1; }
    else return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if(a > b){ a = b; return 1; }
    else return 0;
}
template <typename T>
void iota(std::vector<T>& vec, bool greater = false){
    std::iota(all(vec), 0);
    std::sort(all(vec), [&](int i, int j){
        if(greater) return vec[i] > vec[j];
        return vec[i] < vec[j];
    });
}
// 2つのvectorをマージ
template <typename T>
std::vector<T> vmerge(std::vector<T>& a, std::vector<T>& b){
    std::vector<T> res;
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res));
    return res;
}


// 辺
template <typename T>
class Edge{
public:
    int from, to;
    T cost;
    int ID;
    Edge(int to, T cost) : to(to), cost(cost) {} // for WG
    Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} // for Edges
    Edge(int from, int to, T cost, int ID) : from(from), to(to), cost(cost), ID(ID) {} // for Edges
    bool operator<(const Edge<T>& rhs) const { return cost < rhs.cost; };
    bool operator>=(const Edge<T>& rhs) const { return !(cost < rhs.cost); };
    bool operator>(const Edge<T>& rhs) const { return cost > rhs.cost; };
    bool operator<=(const Edge<T>& rhs) const { return !(cost > rhs.cost); };
    bool operator==(const Edge<T>& rhs) const { return cost == rhs.cost; };
    bool operator!=(const Edge<T>& rhs) const { return !(cost == rhs.cost); };
};
using G = std::vector<std::vector<int>>;
template <typename T>
using WG = std::vector<std::vector<Edge<T>>>;
template <typename T>
using Edges = std::vector<Edge<T>>;

template <typename T, typename F>
// @param ok 解が存在する値
// @param ng 解が存在しない値
// @remark ok > ng の場合は最小値、ok < ng の場合は最大値を返却
T Bsearch(T& ok, T& ng, const F& f){
    while(std::abs(ok-ng) > 1){
        T mid = (ok-ng)/2 + ng;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
template <typename T, typename F>
T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){
    while(itr--){
        T mid = (ok+ng)/2;
        //T mid = sqrtl(ok*ng);
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}


template <typename T>
// @brief (k, n-k)-shuffleである0, 1, ..., N-1 の置換Aを、辞書順で列挙する
bool next_shuffle(std::vector<T>& vec, const int& k){
    int n = vec.size();
    if(n <= k){
        return false;
    }

    // 前K項 := L
    // 後ろN-K項 := R
    auto left = vec.begin();
    auto right = vec.begin() + k;
    T R_max = *std::max_element(right, vec.end());
    T tmp = (std::numeric_limits<T>::min)();
    // @param i Lの要素の中で、Rの要素の最大値よりも小さいもののうち、最大のもののイテレータ(*i := L_(i))
    auto tmpi = left, i = right;
    while(tmpi != right){
        if(tmp <= *tmpi && *tmpi < R_max){
            tmp = *tmpi;
            i = tmpi;
        }
        tmpi++;
    }
    if(i == right){
        return false;
    }

    // @param j Rの要素の中で、L_(i)よりも大きいもののうち、最小のもののイテレータ(*j := R_(j))
    tmp = (std::numeric_limits<T>::max)();
    auto tmpj = right, j = vec.end();
    while(tmpj != vec.end()){
        if(tmp >= *tmpj && *tmpj > *i){
            tmp = *tmpj;
            j = tmpj;
        }
        tmpj++;
    }

    std::iter_swap(i, j); // L_(i)とR_(j)をswap
    i++, j++;
    // やりたいこと：L_(i+1)～L_(k-1)(:= X)とR_(j+1)～R_(n-k-1)(:= Y)を接続し、R_(j+1)が先頭に来るように回転する
    int X_len = k-std::distance(left, i);
    int Y_len = n-k-std::distance(right, j);
    int swap_len = std::min(X_len, Y_len);
    // Xの末尾swap_len項とYの末尾swap_len項をswapする
    std::swap_ranges(right-swap_len, right, j);
    if(swap_len == X_len){
        std::rotate(j, j+swap_len, vec.end());
    }
    else{
        std::rotate(i, right-swap_len, right);
    }

    return true;
}

int log2ll(long long N){
    int B = -1;
    while(N != 0){
        B++;
        N /= 2;
    }
    return B;
}
template <typename T>
// @brief (2,...,2)-shuffleである0, 1, ..., 2*N-1 の置換Aを、辞書順で列挙する
bool next_pairing(std::vector<T>& vec){
    int n = vec.size();
    // @param used vecに含まれるどの数が使用済みであるか
    ll used = 0;
    for(int i = n-1; i >= 0; i--){
        used |= (1<<vec[i]);
        if(i%2 == 1 && vec[i] < log2ll(used)){ // インクリメントできる
            vec[i] = __builtin_ctzll(used >> (vec[i]+1)) + vec[i]+1;
            used ^= (1<<vec[i]);
            for(int j = i+1; j < n; j++){
                vec[j] = __builtin_ctzll(used);
                used ^= (1<<vec[j]);
            }
            return true;
        }
    }
    return false;
}


const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const std::vector<std::tuple<int, int, int>> line3{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}};
const std::vector<std::tuple<int, int, int, int>> line4{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15}, {0,4,8,12}, {1,5,9,13}, {2,6,10,14}, {3,7,11,15}, {0,5,10,15}, {3,6,9,12}};

bool OutOfGrid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}

// @brief 繰り返し二乗法を利用した、x^nの求値
ll power(ll x, ll n){
    ll res = 1;

    while(n){
        if(n & 1) res *= x;
        x *= x;
        n >>= 1;
    }

    return res;
}

ll power_mod(ll x, ll n, const ll& m){
    ll res = 1;

    while(n){
        if(n & 1){
            res = (res*x) % m;
        }
        x = (x*x) % m;
        n >>= 1;
    }

    return res;
}

// @brief x/mのfloor（x/m以下の最大の整数）を求める
ll floor(const ll& x, const ll& m){
    ll r = (x%m + m) % m; // xをmで割った余り
    return (x-r)/m;
}

// @brief x/mのceil（x/m以上の最小の整数）を求める
ll ceil(const ll& x, const ll& m){
    return floor(x+m-1, m); // x/m + (m-1)/m
}

// @brief prefix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> prefix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            sum[i+1][j+1] = f(i, j) + sum[i][j+1] + sum[i+1][j] - sum[i][j];
        }
    }
    return sum;
}

// @brief suffix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和
// @brief f(i, j) := a[i][j]の値
// @rem 貰う遷移で埋めていく
template <typename T>
std::vector<std::vector<T>> suffix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) {
    std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T()));
    for(int i = h-1; i >= 0; i--){
        for(int j = w-1; j >= 0; j--){
            sum[i][j] = f(i, j) + sum[i+1][j] + sum[i][j+1] - sum[i+1][j+1];
        }
    }
    return sum;
}

using namespace std;

#endif
0