oj.uz

Submission #1081686

# Submission time Handle Problem Language Result Execution time Memory
1081686 2024-08-30T09:12:49 Z 42kangaroo Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 36 ms 10076 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(e) == g[st[j].first].end())  break;
					}
					if (j == de[e]) {
						j = de[n] - 1;
						for (; j > de[e]; --j) {
							if (g[st[j].first].find(n) == g[st[j].first].end())  break;
						}
						j++;
					}
					int act = n;
					while (act != st[j].first) {
						cout << act + 1 << " ";
						int be = act;
						for (auto f: g[act]) {
							if (de[f] < de[be] && de[f] >= de[st[j].first]) {
								be = f;
							}
						}
						act = be;
					}
					act = st[j].first;
					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 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 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 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 15 ms 4956 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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