結果

問題 No.3508 OR Mapping
コンテスト
ユーザー cho435
提出日時 2026-04-18 17:02:07
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 471 ms / 2,000 ms
コード長 1,795 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,196 ms
コンパイル使用メモリ 381,628 KB
実行使用メモリ 155,712 KB
最終ジャッジ日時 2026-04-18 17:02:42
合計ジャッジ時間 26,305 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<int>> g(n);
	atcoder::scc_graph sc(n);
	rep(i, 0, m) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		sc.add_edge(u, v);
	}
	auto vv = sc.scc();
	m = vv.size();
	vector<int> id(n, -1);
	vector<vector<int>> sub(n);
	{
		vector<int> nx(m, -1);
		int t = 0;
		for (auto v : vv) {
			for (int x : v) id[x] = t;
			t++;
		}
		if (id[0] != 0) {
			cout << "No\n";
			return;
		}
		rep(i, 0, n) {
			for (int j : g[i]) {
				if (id[i] == id[j]) {
					sub[i].push_back(j);
					continue;
				}
				if (nx[id[i]] == -1) nx[id[i]] = id[j];
				else if (nx[id[i]] != id[j]) chmin(nx[id[i]], id[j]);
			}
		}
		rep(i, 0, m - 1) {
			if (nx[i] != i + 1) {
				cout << "No\n";
				return;
			}
		}
	}
	int b = 0;
	vector<int> col(n, -1);
	rep(i, 0, m) {
		if (vv[i].size() == 1) {
			if (b) {
				b = 0;
				continue;
			} else {
				cout << "No\n";
				return;
			}
		}
		auto dfs = [&](auto self, int nw) -> bool {
			for (int nx : sub[nw]) {
				if (col[nx] != -1) {
					if (col[nx] == col[nw]) return 1;
				} else {
					col[nx] = col[nw] ^ 1;
					if (self(self, nx)) return 1;
				}
			}
			return 0;
		};
		col[vv[i][0]] = 0;
		if (!dfs(dfs, vv[i][0])) {
			cout << "No\n";
			return;
		}
		b = 1;
	}
	cout << "Yes\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0