Submission #1228708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228708		kaiboy	Potemkin cycle (CEOI15_indcyc)	C++20	50 / 100	1101 ms	76316 KiB

indcyc

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100;

int aa[N][N], dd[N], pp[N], qu[N], n;
bool bad[N], visited[N];

bool dfs(int i, int t) {
	if (visited[i])
		return false;
	visited[i] = true;
	if (bad[i])
		return false;
	if (i == t)
		return true;
	for (int j = 0; j < n; j++)
		if (aa[i][j] && dfs(j, t))
			return true;
	return false;
}

int main() {
	int m; cin >> n >> m;
	while (m--) {
		int i, j; cin >> i >> j, i--, j--;
		aa[i][j] = aa[j][i] = true;
	}
	for (int s = 0; s < n; s++)
		for (int t = s + 1; t < n; t++)
			if (!aa[s][t])
				for (int i_ = 0; i_ < n; i_++)
					if (aa[s][i_] && aa[i_][t]) {
						for (int i = 0; i < n; i++) {
							bad[i] = i == i_ || i != s && i != t && aa[i_][i];
							visited[i] = false;
						}
						if (dfs(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 = 0; j < n; j++)
									if (aa[i][j] && !bad[j] && 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: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10