oj.uz

Submission #785029

# Submission time Handle Problem Language Result Execution time Memory
785029 2023-07-17T00:24:44 Z NK_ Potemkin cycle (CEOI15_indcyc) C++17
10 / 100
 15 ms 2088 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	// TIME TO IMPLEMENT FOR 40 MIN TO REALIZE THE IDEA IS WRONG!! 
	// (0-0)

	int N, M; cin >> N >> M;

	V<V<int>> adj(N); for(int e = 0; e < M; e++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}


	V<int> vis(N), low(N), disc(N, -1); int t = 0;

	V<int> stk;
	function<void(int, int)> dfs = [&](int u, int p) {
		// cout << u << " " << p << endl;
		vis[u] = 1;
		disc[u] = ++t; stk.pb(u);
		int best = 0;
		sort(begin(adj[u]), end(adj[u]), [&](int x, int y) {
			return disc[x] > disc[y];
		});

		for(auto& v : adj[u]) if (v != p) {
			if (vis[v]) {
				// back edge -> cycle
				best = max(best, disc[v]);
			} else {
				low[v] = max(low[u], best);
				dfs(v, u);
			}
		}

		int len = disc[u] - best + 1;
		if (low[u] < best && len >= 4) {
			int x = -1; for(auto& v : adj[u]) if (v != p) {
				if (disc[v] == best) x = v;
			}

			while(stk.back() != x) { cout << stk.back() + 1 << " "; stk.pop_back(); }
			cout << x + 1 << nl;
			exit(0);
		}
		--t; stk.pop_back();
	};

	dfs(0, -1);

	cout << "no" << nl;

    return (0-0);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Runtime error 1 ms 340 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 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 1 ms 212 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 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 1 ms 328 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 8 ms 1364 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 4 ms 724 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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