Submission #1081686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081686		42kangaroo	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	36 ms	10076 KiB

indcyc

	//
	// Created by 42kangaroo on 30/08/2024.
	//
	#include "bits/stdc++.h"

	using namespace std;

	using g_t = vector<set<int>>;

	void dfs(int n, int p, int d, g_t& g, vector<pair<int,int>>& st, vector<int>& de) {
		de[n] = d;
		vector<int> up;
		st.push_back({n, de[n] + 1});
		for (auto e: g[n]) {
			if (e == p || de[e] > de[n]) continue;
			if (de[e] != -1) {
				st[de[e]].second++;
				up.push_back(de[e]);
			}
			else dfs(e, n, d + 1, g, st, de);
		}
		std::sort(up.begin(), up.end());
		int i = de[n] - 2;
		for (; i >= 0; --i) {
			if (up.empty() || up.back() != i) break;
			up.pop_back();
		}
		i--;
		for (auto e: g[n]) {
			if (e == p || de[e] > de[n]) continue;
			if (de[e] != -1) {
				if (i > de[e] || st[de[e]].second < de[n]) {
					int j = de[n] - 1;
					for (; j > de[e]; --j) {
						if (g[st[j].first].find(e) == g[st[j].first].end())  break;
					}
					if (j == de[e]) {
						j = de[n] - 1;
						for (; j > de[e]; --j) {
							if (g[st[j].first].find(n) == g[st[j].first].end())  break;
						}
						j++;
					}
					int act = n;
					while (act != st[j].first) {
						cout << act + 1 << " ";
						int be = act;
						for (auto f: g[act]) {
							if (de[f] < de[be] && de[f] >= de[st[j].first]) {
								be = f;
							}
						}
						act = be;
					}
					act = st[j].first;
					while (act != e) {
						cout << act + 1 << " ";
						int be = act;
						for (auto f: g[act]) {
							if (de[f] < de[be] && de[f] >= de[e] ) {
								be = f;
							}
						}
						act = be;
					}
					cout << e + 1;
					exit(0);
				}
			}
		}
		for (auto e: g[n]) {
			if (e == p || de[e] > de[n]) continue;
			if (de[e] != -1) {
				st[de[e]].second--;
			}
		}
		st.pop_back();
	}


	signed main() {
		ios_base::sync_with_stdio(false);
		cin.tie(nullptr);
		int n, m; cin >> n >> m;
		g_t g(n);
		for (int i = 0; i < m; ++i) {
			int a, b; cin >> a >> b;
			g[--a].insert(--b);
			g[b].insert(a);
		}
		vector<int> de(n, -1);
		vector<pair<int,int>> st;
		for (int i = 0; i < n; ++i) {
			if (de[i] == -1) {
				dfs(i, i, 0, g, st, de);
			}
		}
		cout << "no";
	}

• 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