Submission #50096

#	Time	Username	Problem	Language	Result	Execution time	Memory
50096		radoslav11	Potemkin cycle (CEOI15_indcyc)	C++14	60 / 100	1070 ms	3204 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 << 10);

int n, m;
vector<int> adj[MAXN];
bool has[MAXN][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);
	
		has[u][v] = 1;
		has[v][u] = 1;
	}
}

struct dsu
{
	int sz;
	vector<int> par, psz;

	void init(int n)
	{
		sz = n;
		par.assign(sz + 1, 0);
		psz.assign(sz + 1, 0);
		for(int i = 0; i <= sz; i++)
			par[i] = i, psz[i] = 1;
	}

	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
	
	bool connected(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y)
	{
		x = root(x), y = root(y);
		if(x == y) return;
		if(psz[x] > psz[y]) swap(x, y);
		par[x] = y, psz[y] += psz[x]; 
	}
};

bool rhas[MAXN];
bool used[MAXN];
bool ok[MAXN][MAXN];

void dfs(int u, int rt)
{
	used[u] = 1;
	for(int v: adj[u])
		if(!used[v] && !rhas[v])
			dfs(v, rt);
		else if(rhas[v])
			ok[rt][v] = 1;
}

int par[MAXN];

void solve(int rt, int l, int r)
{
	queue<int> q;
	memset(par, -1, sizeof(par));
	
	q.push(l);
	par[l] = rt;
	par[rt] = 0;
	
	while(!q.empty())
	{
		int u = q.front();
		q.pop();

		for(int v: adj[u])
			if(par[v] == -1 && (!rhas[v] || v == r))
			{
				q.push(v);
				par[v] = u;
			}
	}

	if(par[r] == -1) return;

	int x = r;
	while(x)
	{
		cout << x << " ";
		x = par[x];
	}

	cout << endl;
	exit(0);
}

void solve()
{
	for(int root = 1; root <= n; root++)
	{
		for(int i = 1; i <= n; i++) used[i] = 0, rhas[i] = 0;

		used[root] = 1;
		for(int v: adj[root])
			rhas[v] = 1;
		
		for(int v: adj[root])
			for(int u: adj[root])
				ok[u][v] = 0;

		for(int v: adj[root]) dfs(v, v);		

		for(int v: adj[root])
			for(int u: adj[root])
				if(v < u && !has[u][v] && (ok[u][v] || ok[v][u]))
					solve(root, u, v);
	}

	cout << "no" << endl; 
}

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

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

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