oj.uz

답안 #787238

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787238 2023-07-19T00:02:04 Z NK_ Potemkin cycle (CEOI15_indcyc) C++17
0 / 100
 223 ms 3520 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>;

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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Integer 0 violates the range [1, 4]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Integer 0 violates the range [1, 10]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 244 KB Integer 0 violates the range [1, 10]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Integer 0 violates the range [1, 100]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 340 KB Integer 0 violates the range [1, 100]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 468 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 484 KB Integer 0 violates the range [1, 300]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 107 ms 2284 KB Integer 0 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 1228 KB Integer 0 violates the range [1, 1000]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 223 ms 3520 KB Integer 0 violates the range [1, 440]
2 Halted 0 ms 0 KB -