oj.uz

Submission #36905

# Submission time Handle Problem Language Result Execution time Memory
36905 2017-12-17T16:17:55 Z aome Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 66 ms 4120 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3196 KB Output is correct
2 Incorrect 0 ms 3196 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3196 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3196 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3196 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3196 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3196 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3196 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 3724 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3460 KB Repeated vertex
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 4120 KB Repeated vertex
2 Halted 0 ms 0 KB -