Submission #50040

#	Time	Username	Problem	Language	Result	Execution time	Memory
50040		radoslav11	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	39 ms	26220 KiB

indcyc

#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n, m, disc[MAXN], low[MAXN], dfs_time;
vector<int> adj[MAXN];

void read()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

int par[MAXN], dep[MAXN], ver[MAXN];

void tarjan(int u, int pr = -1)
{
	disc[u] = ++dfs_time;
	ver[dfs_time] = u;
	low[u] = pr == -1 ? 0 : low[pr];
	dep[u] = pr == -1 ? 0 : (dep[pr] + 1);

	int closest = 0;
	for(int v: adj[u])
		if(v != pr && disc[v])
			chkmax(closest, disc[v]);

	for(int v: adj[u])
		if(v != pr && disc[v] > low[u] && closest == disc[v] && dep[u] - dep[v] >= 3)
		{
			int x = u;
			while(x != v)
			{
				cout << x << " ";
				x = par[x];
			}

			cout << v << endl;
			exit(0);
		}

	chkmax(low[u], closest);
	for(int v: adj[u])
		if(v != pr && !disc[v])
		{
			par[v] = u;
			tarjan(v, u);


		}
}

void solve()
{
	for(int i = 1; i <= n; i++)
		if(!disc[i]) tarjan(i);

	cout << "no" << endl; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 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