Submission #787238

#	Time	Username	Problem	Language	Result	Execution time	Memory
787238		NK_	Potemkin cycle (CEOI15_indcyc)	C++17	0 / 100	223 ms	3520 KiB

indcyc

// 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>;

const int LG = 20;
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, 0), low(N, -1), disc(N, -1); int t = 0;
	V<V<int>> good(N);

	V<V<int>> up(N, V<int>(LG, -1));

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};

	auto lca = [&](int a, int b) {
		if (disc[a] < disc[b]) swap(a, b);
		a = jmp(a, disc[a] - disc[b]);

		if (a == b) return a;
		for(int i = LG - 1; i >= 0; i--) {
			if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
		}

		return up[a][0];
	};

	V<int> stk = {-1};
	function<void(int, int)> dfs = [&](int u, int p) {
		cout << u << endl;
		up[u][0] = (p == -1 ? u : p);
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		vis[u] = 1;
		disc[u] = ++t; stk.pb(u);
		int best = -1;
		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]) {
				cout << u << " " << v << endl;
				// back edge -> cycle
				best = max(best, disc[v]);
			} else {
				low[v] = max(low[u], best);
				dfs(v, u);
			}
		}

		if (size(good[u])) {
			for(auto x : good[u]) for(auto y : good[u]) if (x < y) {
				cout << u << " " << x << " " << y << endl;
				int l = lca(x, y);
				if (max(low[x], low[y]) >= disc[l]) continue;

				V<int> ans = {u};
				int k = x;
				while(k != l) {
					ans.pb(k);
					k = up[k][0];
				}
				ans.pb(l);

				V<int> dwn;
				k = y;
				while(k != l) {
					dwn.pb(k);
					k = up[k][0];
				}
				dwn.pb(k);

				dwn.pop_back(); reverse(begin(dwn), end(dwn));
				for(auto c : dwn) ans.pb(c);
			}
		}

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

		if (low[u] < best) {
			
			assert(x != -1);
			
			cout << u << " -> " << x << endl;
			if (len >= 4) {
				while(stk.back() != x) { cout << stk.back() + 1 << " "; stk.pop_back(); }
				cout << x + 1 << nl;
				exit(0);
			}
		}

		if (x != -1) good[x].pb(u);

		--t; stk.pop_back();
	};

	dfs(0, -1);

	cout << "no" << nl;

    return (0-0);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10