Submission #82396

#	Time	Username	Problem	Language	Result	Execution time	Memory
82396		aminra	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	1077 ms	34364 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = (int)1e5+ 3;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int n, m, visited[MAXN];
set<int> G[MAXN], G2[MAXN];
vector<int> ans;
pair<int, int> cor(pair<int, int> p)
{
	return {min(p.first, p.second), max(p.first, p.second)};
}
void dfs(int u, int to)
{
	if(visited[to])
		return;
	visited[u] = 1;
	ans.push_back(u);
	for (auto v : G2[u])
		if(!visited[v])
			dfs(v, to);
	if(!visited[to])
		ans.pop_back();
}
bool check(int i, int u)
{
	set< pair<int, int> > del;
	del.insert(cor({i, u}));
	for (int j = 1; j <= n; j++)
		for (auto c : G[j])
			G2[j].insert(c);
		
	for (int j = 1; j <= n; j++)
		if(G2[i].find(j) != G2[i].end() && G2[u].find(j) != G2[u].end())
		{
			for (auto c : G2[j])
				del.insert(cor({j, c}));
		}
	for (auto pai : del)
		G2[pai.first].erase(pai.second), G2[pai.second].erase(pai.first);
	memset(visited, 0, sizeof visited);
	dfs(i, u);
	return visited[u];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		G[u].insert(v);
		G[v].insert(u);
	}
	for (int i = 1; i <= n; i++)
	{
		for (auto u : G[i])
		{
			if(check(i, u))
			{
				for (auto v : ans)
					cout << v << " ";
				return 0;
			}
		}
	}
	cout << "no";
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10