結果

問題 No.2494 Sum within Components
ユーザー otamay6
提出日時 2023-10-16 16:26:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 173 ms / 2,000 ms
コード長 863 bytes
コンパイル時間 629 ms
コンパイル使用メモリ 71,424 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 22:14:17
合計ジャッジ時間 2,282 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<utility>
#define int long long
struct uf{
    std::vector<int> r;
    uf(int n):r(std::vector<int>(n+1, -1)){};
    void change(int u, int val){
        r[u] = -val;
    }
    int root(int u){
        if(r[u]<=0){
            return u;
        }
        else{
            return r[u] = root(r[u]);
        }
    }
    int size(int u){
        return -r[root(u)];
    }
    bool connect(int a,int b){
        if(size(a) < size(b)){
            std::swap(a,b);
        }
        if(root(a) == root(b)){
            return false;
        }
        a = root(a);
        b = root(b);
        r[a] += r[b];
        r[b] = a;
        return true;
    }
};
signed main(void){
    int n,m;
    std::cin>>n>>m;
    uf g(n);
    for(int i = 0; i < n; i++){
        int a;std::cin>>a;
        g.change(i+1, a);
    }
    while(m--){
        int u,v;
        std::cin>>u>>v;
        g.connect(u,v);
    }
    int res = 1;
    for(int i=0; i < n; i++){
        res *= g.size(1+i) % 998244353;
        res %= 998244353;
    }
    std::cout << res << std::endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0