結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー startcpp
提出日時 2026-01-11 16:24:56
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 323 ms / 2,000 ms
コード長 1,601 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,229 ms
コンパイル使用メモリ 121,552 KB
実行使用メモリ 21,760 KB
最終ジャッジ日時 2026-01-11 16:25:00
合計ジャッジ時間 2,634 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// 「連結」じゃん！！！
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#include <cassert>
#include <atcoder/modint>
#include <atcoder/dsu>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
using namespace atcoder;
using mint = modint998244353;

int n, m, K;
vector<vector<int>> et;
vector<int> U, V;
vector<int> b;

// 二部グラフ判定か！！！
bool solve() {
	vector<int> color(n, -1);
	queue<int> que;

	bool binary = true;
	que.push(0);
	color[0] = 0;
	while (!que.empty()) {
		int v = que.front();
		que.pop();
		for (int nv: et[v]) {
			if (color[nv] == -1) {
				color[nv] = !color[v];
				que.push(nv);
			}
			else if (color[nv] == color[v]) {
				binary = false;
				break;
			}
		}
	}

	int i;
	if (!binary) {
		if (K % 2 == 1) return true;
		int res = 0;
		rep(i, n) res += b[i];
		return res % 2 == 0;
	}

	int x = 0, y = 0;
	rep(i, n) {
		if (color[i] == 0) x += b[i];
		else y += b[i];
	}

	return x % K == y % K;
}

signed main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> K;
		et.clear();
		et.resize(n);
		U.clear();
		V.clear();

		int i;
		rep(i, m) {
			int u, v;
			cin >> u >> v; u--; v--;
			et[u].push_back(v);
			et[v].push_back(u);
			U.push_back(u);
			V.push_back(v);
		}
		
		b.clear();
		b.resize(n);
		rep(i, n) { cin >> b[i]; }

		bool res = solve();
		if (res) { cout << "Yes" << endl; }
		else { cout << "No" << endl; }
	}
	return 0;
}
0