Submission #1231351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231351		kaiboy	Potemkin cycle (CEOI15_indcyc)	C++20	100 / 100	255 ms	2212 KiB

indcyc

// coached by rainboy
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1000;

vector<int> ej[N];
bool aa[N][N], visited[N], inqu[N];
int dd[N], pp[N], qu[N], cnt;

void dfs(int i, int i_) {
	if (i == i_)
		return;
	if (aa[i][i_]) {
		if (!inqu[i])
			inqu[qu[cnt++] = i] = true;
		return;
	}
	if (visited[i])
		return;
	visited[i] = true;
	for (int j : ej[i])
		dfs(j, i_);
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m; cin >> n >> m;
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		ej[i].push_back(j);
		ej[j].push_back(i);
		aa[i][j] = aa[j][i] = true;
	}
	for (int i_ = 0; i_ < n; i_++) {
		for (int i = 0; i < n; i++)
			visited[i] = false;
		visited[i_] = true;
		for (int i = 0; i < n; i++)
			if (!aa[i][i_] && !visited[i]) {
				cnt = 0, dfs(i, i_);
				for (int g = 0; g < cnt; g++) {
					int s = qu[g]; inqu[s] = false;
					for (int h = g + 1; h < cnt; h++) {
						int t = qu[h];
						if (!aa[s][t]) {
							for (int i = 0; i < n; i++)
								dd[i] = n;
							int cnt = 0; dd[s] = 0, pp[s] = -1, qu[cnt++] = s;
							for (int h = 0; h < cnt; h++) {
								int i = qu[h], d = dd[i] + 1;
								for (int j : ej[i])
									if (j != i_ && (j == t || !aa[j][i_]) && dd[j] == n)
										dd[j] = d, pp[j] = i, qu[cnt++] = j;
							}
							cout << s + 1 << ' ' << i_ + 1;
							for (int i = t; i != s; i = pp[i])
								cout << ' ' << i + 1;
							cout << '\n';
							return 0;
						}
					}
				}
			}
	}
	cout << "no\n";
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10