結果

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

ソースコード

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+= dfs(j,adj,visited,a);
		}
	}
	return total+a[i];
}

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