Submission #1258968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258968		nqknht	Potemkin cycle (CEOI15_indcyc)	C++20	30 / 100	12 ms	1348 KiB

indcyc

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
int n, m;
vector<int> g[2005];
namespace sub1
{
	int dem = 0, lu = 0;
	bool kt = false;
	int num[305], h[305], cha[305], low[305], pos[305];
	void dfs(int i, int pa)
	{
		if (kt == true)
			return;
		dem++;
		num[i] = dem;
		low[i] = dem;
		pos[dem] = i;
		h[i] = h[pa] + 1;
		cha[i] = pa;
		int d = 0, luu;
		for (auto j : g[i])
		{
			if (j == pa)
				continue;
			if (num[j] != 0)
			{
				if (num[j] == 1)
				{
					d++;
					continue;
				}
				low[i] = min(low[i], low[j]);
				h[i] = h[pos[low[i]]] + 1;
				cha[i] = pos[low[i]];
			}
		}
		if (d == 1)
		{
			if (h[i] >= 4)
			{
				kt = true;
				lu = i;
				return;
			}
			low[i] = 1;
			h[i] = 2;
			cha[i] = pos[1];
		}
		for (auto j : g[i])
		{
			if (j == pa || num[j] != 0)
				continue;
			dfs(j, i);
		}
	}
	void xuly()
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				num[j] = 0, h[j] = 0, low[j] = 0;
			dem = 0;
			dfs(i, i);
			if (kt == true)
			{
				vector<int> v;
				while (lu != i)
					v.push_back(lu), lu = cha[lu];
				v.push_back(i);
				reverse(v.begin(), v.end());
				for (auto j : v)
					cout << j << " ";
				return;
			}
		}
		if(n < 7)
		cout << "no";
	}
}
namespace full
{
	int dem = 0, lu = 0;
	bool kt = false;
	int num[1005], h[1005], cha[1005], low[1005], pos[1005];
	void dfs(int i, int pa)
	{
		if (kt == true)
			return;
		dem++;
		num[i] = dem;
		low[i] = dem;
		pos[dem] = i;
		h[i] = h[pa] + 1;
		cha[i] = pa;
		int d = 0, luu;
		for (auto j : g[i])
		{
			if (j == pa)
				continue;
			if (num[j] != 0)
			{
				if (num[j] == 1)
				{
					d++;
					continue;
				}
				low[i] = min(low[i], low[j]);
				h[i] = h[pos[low[i]]] + 1;
				cha[i] = pos[low[i]];
			}
		}
		if (d == 1)
		{
			if (h[i] >= 4)
			{
				kt = true;
				lu = i;
				return;
			}
			low[i] = 1;
			h[i] = 2;
			cha[i] = pos[1];
		}
		for (auto j : g[i])
		{
			if (j == pa || num[j] != 0)
				continue;
			dfs(j, i);
		}
	}
	void xuly()
	{
		for (int i = 1; i <= 10; i++)
		{
			for (int j = 1; j <= n; j++)
				num[j] = 0, h[j] = 0, low[j] = 0;
			dem = 0;
			dfs(i, i);
			if (kt == true)
			{
				vector<int> v;
				while (lu != i)
					v.push_back(lu), lu = cha[lu];
				v.push_back(i);
				reverse(v.begin(), v.end());
				for (auto j : v)
					cout << j << " ";
				return;
			}
		}
		// if/
		cout << "no";
	}
}
int main()
{
	//    if (fopen("special.inp","r")){
	//        freopen("special.inp","r",stdin);
	//        freopen("special.out","w",stdout);
	//    }
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	if (n <= 300 && m <= 2000)
		return sub1::xuly(), 0;
	full::xuly();
}

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