oj.uz

Submission #1081579

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

using namespace std;

using g_t = vector<vector<int>>;

void dfs(int n, int p, int d, g_t& g, vector<int>& hi, vector<int>& de) {
	de[n] = d;
	for (auto e: g[n]) {
		if (e == p || de[e] > de[n]) continue;
		if (de[e] != -1) {
			hi[n] = max(hi[n], de[e]);
		}
		else dfs(e, n, d + 1, g, hi, de);
	}
}

void dfs2(int n, g_t& g, vector<int>& st, vector<int>& hi, vector<int>& de, vector<bool>& vis) {
	st.push_back(n);
	vis[n] = true;
	for (auto e: g[n]) {
		if (vis[e]) continue;
		else dfs2(e, g, st, hi, de, vis);
	}
	if (hi[n] > -1 && de[n] - hi[n] >= 3) {
		int maHi = -1;
		for (int i = de[n] - 1; i > hi[n]; --i) {
			maHi = max(maHi, hi[st[i]]);
		}
		if (maHi < hi[n]) {
			for (int i = de[n]; i >= hi[n]; --i) {
				cout << st[i] + 1 << " ";
			}
			exit(0);
		}
	}
	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].push_back(--b);
		g[b].push_back(a);
	}
	vector<int> hi(n, -1), de(n, -1), st;
	vector<bool> vis(n, false);
	for (int i = 0; i < n; ++i) {
		if (!vis[i]) {
			dfs(i, i, 0, g, hi, de);
			dfs2(i, g, st, hi, de, vis);
		}
	}
	cout << "no";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Incorrect 1 ms 520 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1400 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 720 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2156 KB Output is correct
2 Correct 10 ms 2140 KB Output is correct
3 Incorrect 10 ms 1748 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -