Submission #1081579

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

indcyc

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

using namespace std;

using g_t = vector<vector<int>>;

void dfs(int n, int p, int d, g_t& g, vector<int>& hi, vector<int>& de) {
	de[n] = d;
	for (auto e: g[n]) {
		if (e == p || de[e] > de[n]) continue;
		if (de[e] != -1) {
			hi[n] = max(hi[n], de[e]);
		}
		else dfs(e, n, d + 1, g, hi, de);
	}
}

void dfs2(int n, g_t& g, vector<int>& st, vector<int>& hi, vector<int>& de, vector<bool>& vis) {
	st.push_back(n);
	vis[n] = true;
	for (auto e: g[n]) {
		if (vis[e]) continue;
		else dfs2(e, g, st, hi, de, vis);
	}
	if (hi[n] > -1 && de[n] - hi[n] >= 3) {
		int maHi = -1;
		for (int i = de[n] - 1; i > hi[n]; --i) {
			maHi = max(maHi, hi[st[i]]);
		}
		if (maHi < hi[n]) {
			for (int i = de[n]; i >= hi[n]; --i) {
				cout << st[i] + 1 << " ";
			}
			exit(0);
		}
	}
	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].push_back(--b);
		g[b].push_back(a);
	}
	vector<int> hi(n, -1), de(n, -1), st;
	vector<bool> vis(n, false);
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i, i, 0, g, hi, de);
			dfs2(i, g, st, hi, de, vis);
		}
	}
	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