結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー askr58
提出日時 2026-01-11 15:37:24
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 292 ms / 2,000 ms
コード長 850 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,122 ms
コンパイル使用メモリ 348,124 KB
実行使用メモリ 31,556 KB
最終ジャッジ日時 2026-01-11 15:37:41
合計ジャッジ時間 5,456 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include <atcoder/dsu>
int main(){
	int ttt;
	cin>>ttt;
	while(ttt--){
		int n,m,k;
		cin>>n>>m>>k;
		vector<vector<int>> graph(n);
		atcoder::dsu uf(2*n);
		vector<ll> b(n);
		for(int i=0;i<m;i++){
			int u,v;
			cin>>u>>v;
			u--;v--;
			graph[u].push_back(v);
			graph[v].push_back(u);
			uf.merge(u,v+n);
			uf.merge(v,u+n);
		}
		for(int i=0;i<n;i++)cin>>b[i];
		if(uf.groups().size()==1){
			if(k%2){
				cout<<"Yes"<<endl;
			}else{
				ll sum=0;
				for(int i=0;i<n;i++)sum+=b[i];
				if(sum%2==0)cout<<"Yes"<<endl;
				else cout<<"No"<<endl;
			}
		}else{
			auto vv=uf.groups();
			ll sum=0;
			for(int i=0;i<n;i++){
				if(vv[0][i]<n)sum+=b[vv[0][i]];
				if(vv[1][i]<n)sum-=b[vv[1][i]];
			}
			if(sum%k==0)cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}
	}
}
0