結果

問題 No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
コンテスト
ユーザー edenooo
提出日時 2023-07-25 07:04:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 5,000 ms
コード長 3,622 bytes
コンパイル時間 2,312 ms
コンパイル使用メモリ 215,312 KB
最終ジャッジ日時 2025-02-15 18:52:50
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 39
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

pair<vector<int>, vector<int> > BipartiteMatching(int L, int R, const vector<pair<int, int> > &e) {
	vector<vector<int> > g(L);
	for(auto [a,b] : e)
		g[a].push_back(b);

	vector<int> matL(L, -1), matR(R, -1);
	vector<bool> vis(L);
	auto DFS = [&](auto &self, int n)->bool {
		if (vis[n]) return false;
		vis[n] = true;
		for(int next : g[n])
			if (matR[next] == -1)
			{
				matL[n] = next, matR[next] = n;
				return true;
			}
		for(int next : g[n])
			if (self(self, matR[next]))
			{
				matL[n] = next, matR[next] = n;
				return true;
			}
		return false;
	};

	for(int i=0; i<L; i++)
	{
		fill(vis.begin(), vis.end(), false);
		DFS(DFS, i);
	}
	return {matL, matR};
}

pair<int, vector<int> > StronglyConnectedComponents(int N, const vector<pair<int, int> > &e) {
	vector<vector<int> > g(N), rg(N);
	for(auto [a,b] : e)
		g[a].push_back(b), rg[b].push_back(a);

	vector<bool> vis(N);
	vector<int> stk;
	auto DFS = [&](auto &self, int n)->void {
		vis[n] = true;
		for(int next : g[n])
			if (!vis[next])
				self(self, next);
		stk.push_back(n);
	};
	for(int n=0; n<N; n++)
		if (!vis[n])
			DFS(DFS, n);

	int SCC = 0;
	vector<int> myscc(N);
	auto DFS2 = [&](auto &self, int n)->void {
		vis[n] = true;
		for(int next : rg[n])
			if (!vis[next])
				self(self, next);
		myscc[n] = SCC;
	};
	fill(vis.begin(), vis.end(), false);
	while(!stk.empty())
	{
		int n = stk.back(); stk.pop_back();
		if (vis[n]) continue;
		DFS2(DFS2, n);
		SCC++;
	}
	return {SCC, myscc};
}

vector<pair<vector<int>, vector<int> > > DulmageMendelsohn(int L, int R, const vector<pair<int, int> > &e) {
	auto [matL, matR] = BipartiteMatching(L, R, e);
	vector<int> mat(L+R);
	for(int i=0; i<L; i++)
		mat[i] = (matL[i] == -1 ? -1 : L+matL[i]);
	for(int i=L; i<L+R; i++)
		mat[i] = matR[i-L];

	vector<vector<int> > g(L+R);
	for(auto [a,b] : e)
	{
		g[a].push_back(L+b);
		g[L+b].push_back(a);
	}
	vector<int> col(L+R, -1); // (-1, 0, 1) = (U, E, O)
	auto DFS = [&](auto &self, int n)->void {
		col[n] = 0;
		for(int next : g[n])
		{
			col[next] = 1;
			if (col[mat[next]] == -1)
				self(self, mat[next]);
		}
	};
	for(int i=0; i<L+R; i++)
		if (mat[i] == -1)
			DFS(DFS, i);

	vector<pair<int, int> > E; // directed edges
	for(auto [a,b] : e)
		if (col[a] == -1 && col[L+b] == -1)
			E.push_back({a, L+b});
	for(int i=0; i<L; i++)
		if (col[i] == -1 && mat[i] != -1)
			E.push_back({mat[i], i});
	auto [K, myscc] = StronglyConnectedComponents(L+R, E);

	vector<pair<vector<int>, vector<int> > > ret(K+2);
	for(int i=0; i<L; i++)
		if (matL[i] != -1)
		{
			if (col[i] == 1) ret[0].first.push_back(i), ret[0].second.push_back(matL[i]);
			else if (col[i] == 0) ret[K+1].first.push_back(i), ret[K+1].second.push_back(matL[i]);
			else ret[myscc[i]+1].first.push_back(i), ret[myscc[i]+1].second.push_back(matL[i]);
		}
	for(int i=0; i<L; i++)
		if (matL[i] == -1)
			ret[K+1].first.push_back(i);
	for(int i=0; i<R; i++)
		if (matR[i] == -1)
			ret[0].second.push_back(i);
	return ret;
};

int N, M, L;

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	cin >> N >> M >> L;
	vector<pair<int, int> > e;
	for(int i=0; i<L; i++)
	{
		int a, b;
		cin >> a >> b;
		a--; b--; // 0-based
		e.push_back({a, b});
	}
	auto v = DulmageMendelsohn(N, M, e);
	vector<int> pos(N+M);
	for(int i=0; i<v.size(); i++)
	{
		for(int j : v[i].first) pos[j] = i;
		for(int j : v[i].second) pos[N+j] = i;
	}

	for(auto [a,b] : e)
	{
		if (pos[a] == pos[N+b] && v[pos[a]].first.size() + v[pos[a]].second.size() == 2) cout << "No\n";
		else cout << "Yes\n";
	}
	return 0;
}
0