Submission #1081658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081658		42kangaroo	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	1068 ms	77392 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(n) == g[st[j].first].end() || g[st[j].first].find(e) == g[st[j].first].end())  break;
				}
				int act = n;
				while (act != j) {
					cout << act + 1<< " ";
					int be = act;
					for (auto f: g[act]) {
						if (de[f] < de[be] && de[f] >= de[j] ) {
							be = f;
						}
					}
					act = be;
				}
				act = j;
				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: 10 / 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