結果

問題 No.2494 Sum within Components
コンテスト
ユーザー Muhammad Ashar Usmani
提出日時 2025-11-17 10:55:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 277 ms / 2,000 ms
コード長 1,305 bytes
コンパイル時間 1,937 ms
コンパイル使用メモリ 201,156 KB
実行使用メモリ 18,288 KB
最終ジャッジ日時 2025-11-17 10:55:21
合計ジャッジ時間 4,380 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;


int dfs(int i, vector<vector<int>>&adj, vector<bool>&visited, vector<int>&a) {

    visited[i] = true;

    int total = 0;

    for (int j : adj[i]) {
        if (visited[j] == false) {

            total  = (total + dfs(j, adj, visited, a)) % 998244353;
        }
    }
    return (total + a[i]) % 998244353;
}

void dfs1(vector<int>&sum, int sum1, vector<vector<int>>&adj, int u) {

    sum[u] = sum1;
    for (int i : adj[u]) {
        if (sum[i] == -1) {
            dfs1(sum, sum1, adj, i);
        }
    }
}
signed main() {

    int n, m;
    cin >> n >> m;

    vector<vector<int>>adj(n + 1);
    vector<int>a(n + 1);

    for (int i = 1; i <= n; ++i)cin >> a[i];
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> sum(n + 1, -1);
    vector<bool>visited(n + 1, false);
    for (int i = 1; i <= n; ++i) {

        if (visited[i] == false) {
            //find sum of component

            int sum1 = dfs(i, adj, visited, a);

            dfs1(sum, sum1, adj, i);

        }
    }
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans = (ans * sum[i]) % 998244353;
    }

    cout << ans % 998244353 << endl;




}
0