#895122 (C++17) No.1744 Selfish Spies 1 (à la Princess' Perfectionism)

提出ソース

結果

問題	No.1744 Selfish Spies 1 (à la Princess' Perfectionism)
ユーザー	edenooo
提出日時	2023-07-25 07:04:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	39 ms / 5,000 ms
コード長	3,622 bytes
コンパイル時間	2,580 ms
コンパイル使用メモリ	221,168 KB
実行使用メモリ	7,668 KB
最終ジャッジ日時	2024-10-02 01:35:14
合計ジャッジ時間	4,651 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	1 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	2 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	3 ms 5,248 KB
testcase_17	AC	3 ms 5,248 KB
testcase_18	AC	3 ms 5,248 KB
testcase_19	AC	2 ms 5,248 KB
testcase_20	AC	2 ms 5,248 KB
testcase_21	AC	2 ms 5,248 KB
testcase_22	AC	2 ms 5,248 KB
testcase_23	AC	2 ms 5,248 KB
testcase_24	AC	7 ms 5,248 KB
testcase_25	AC	3 ms 5,248 KB
testcase_26	AC	4 ms 5,248 KB
testcase_27	AC	5 ms 5,248 KB
testcase_28	AC	30 ms 7,548 KB
testcase_29	AC	4 ms 5,248 KB
testcase_30	AC	4 ms 5,248 KB
testcase_31	AC	5 ms 5,248 KB
testcase_32	AC	4 ms 5,248 KB
testcase_33	AC	28 ms 7,668 KB
testcase_34	AC	27 ms 7,544 KB
testcase_35	AC	37 ms 7,504 KB
testcase_36	AC	39 ms 7,632 KB
testcase_37	AC	36 ms 7,628 KB
testcase_38	AC	33 ms 7,636 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}

yukicoder

結果

テストケース

ソースコード