Submission #36905

#	Time	Username	Problem	Language	Result	Execution time	Memory
36905		aome	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	66 ms	4120 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m;
int par[N];
int in[N];
bool flag[N][N];
vector<int> G[N];

void dfs(int u, int r) {
	in[u] = r;
	for (auto v : G[u]) {
		if (par[v] == u) dfs(v, r);
	}
}

void trace(int r, int x, int y) {
	vector<int> vx, vy;
	while (x != r) vx.push_back(x), x = par[x];
	vx.push_back(r);
	while (y != r) vy.push_back(y), y = par[y];
	reverse(vy.begin(), vy.end());
	for (auto i : vy) vx.push_back(i);
	for (auto i : vx) cout << i << ' '; exit(0); 
}

void solve(int r) {
	queue<int> qu;
	for (int i = 1; i <= n; ++i) par[i] = 0;
	par[r] = r, qu.push(r);
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (auto v : G[u]) {
			if (!par[v]) {
				par[v] = u, qu.push(v);
			}
		}
	}
	for (auto u : G[r]) dfs(u, u);
	for (int i = 1; i <= n; ++i) {
		if (i == r) continue;
		for (auto v : G[i]) {
			if (par[i] == r && par[v] == r) flag[i][v] = 1;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (auto v : G[i]) {
			if (par[v] != i && par[i] != v && !flag[in[v]][in[i]]) {
				trace(r, v, i);
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		if (i == r) continue;
		for (auto v : G[i]) {
			if (par[i] == r && par[v] == r) flag[i][v] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) solve(i);
	cout << "no";
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 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