Submission #247046

#	Time	Username	Problem	Language	Result	Execution time	Memory
247046		Sprdalo	Potemkin cycle (CEOI15_indcyc)	C++17	10 / 100	1091 ms	2144 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 1010;
int n, m;
bool ok = 0;
vi e[maxn], vis(maxn);

stack<int> s;

void solve(){
	while(!s.empty()){
		cout << s.top() << ' ';
		s.pop();
	}
	cout << '\n';
	exit(0);
}

vi ud(maxn, 0);

void dfs(int x, int c, int st){


	vis[x]++;
	s.push(x);
	//cout << "USO " << x << ' ' << c << endl;

	for (auto& i : e[x]){
		if (i == st){
			if (c >= 4) solve();
			continue;
		}

		if (vis[i] || (ud[i] && c < 3)){
			++vis[i];
			continue;
		}

		++vis[i];

		dfs(i, c + 1, st);
	}

	for (auto& i : e[x])
		if (i != st)
			--vis[i];

	--vis[x];
	//cout << "IZASO " << x << '\n';
	s.pop();
}

void init(){
	for (int i = 1; i <= n; ++i){
		vis[i] = 0;
	}
	while(!s.empty()) s.pop();
}

signed main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cerr.tie(nullptr);	

	cin >> n >> m;

	for (int i = 0; i < m; ++i){
		int u, v;
		cin >> u >> v;

		e[u].push_back(v);
		e[v].push_back(u);
	}

	for (int i = 1; i <= n; ++i){
		init();
		//if (i != 2) continue;
		s.push(i);
		for (auto& j : e[i])
			ud[j] = 1;
		for (auto& j : e[i]){
			dfs(j,2,i);
		}
	}

	cout << "no\n";
}

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