oj.uz

Submission #1081658

# Submission time Handle Problem Language Result Execution time Memory
1081658 2024-08-30T08:52:13 Z 42kangaroo Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 1000 ms 77392 KB 
//
// Created by 42kangaroo on 30/08/2024.
//
#include "bits/stdc++.h"

using namespace std;

using g_t = vector<set<int>>;

void dfs(int n, int p, int d, g_t& g, vector<pair<int,int>>& st, vector<int>& de) {
	de[n] = d;
	vector<int> up;
	st.push_back({n, de[n] + 1});
	for (auto e: g[n]) {
		if (e == p || de[e] > de[n]) continue;
		if (de[e] != -1) {
			st[de[e]].second++;
			up.push_back(de[e]);
		}
		else dfs(e, n, d + 1, g, st, de);
	}
	std::sort(up.begin(), up.end());
	int i = de[n] - 2;
	for (; i >= 0; --i) {
		if (up.empty() || up.back() != i) break;
		up.pop_back();
	}
	i--;
	for (auto e: g[n]) {
		if (e == p || de[e] > de[n]) continue;
		if (de[e] != -1) {
			if (i > de[e] || st[de[e]].second < de[n]) {
				int j = de[n] - 1;
				for (; j > de[e]; --j) {
					if (g[st[j].first].find(n) == g[st[j].first].end() || g[st[j].first].find(e) == g[st[j].first].end())  break;
				}
				int act = n;
				while (act != j) {
					cout << act + 1<< " ";
					int be = act;
					for (auto f: g[act]) {
						if (de[f] < de[be] && de[f] >= de[j] ) {
							be = f;
						}
					}
					act = be;
				}
				act = j;
				while (act != e) {
					cout << act + 1 << " ";
					int be = act;
					for (auto f: g[act]) {
						if (de[f] < de[be] && de[f] >= de[e] ) {
							be = f;
						}
					}
					act = be;
				}
				cout << e + 1;
				exit(0);
			}
		}
	}
	for (auto e: g[n]) {
		if (e == p || de[e] > de[n]) continue;
		if (de[e] != -1) {
			st[de[e]].second--;
		}
	}
	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].insert(--b);
		g[b].insert(a);
	}
	vector<int> de(n, -1);
	vector<pair<int,int>> st;
	for (int i = 0; i < n; ++i) {
		if (de[i] == -1) {
			dfs(i, i, 0, g, st, de);
		}
	}
	cout << "no";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Too short sequence

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Too short sequence
2 Incorrect 0 ms 348 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1053 ms 39368 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 56332 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 5468 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 28660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10836 KB Too short sequence
2 Correct 52 ms 10836 KB Output is correct
3 Execution timed out 1008 ms 77392 KB Time limit exceeded
4 Halted 0 ms 0 KB -