Submission #365990

#	Time	Username	Problem	Language	Result	Execution time	Memory
365990		kostia244	Potemkin cycle (CEOI15_indcyc)	C++17	100 / 100	779 ms	5876 KiB

indcyc

#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 1002, maxm = 2e5 + 3;
int can[maxm][maxn], hv[maxn][maxn], vis[maxm], n, m;
vector<array<int, 2>> edges;
vector<int> cur;
void reduce() {
	int r = 0, l = 0;
	[&]() {
	while(r < cur.size()) {
		for(int i = r-2; i >= 0; i--) {
			if(hv[cur[r]][cur[i]]) {
				l = i;
				r++;
				return;
			}
		}
		r++;
	}
	}();
	for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
	exit(0);
}
void dfs(int ed) {
	vis[ed] = 2;
	auto [st, en] = edges[ed];
	cur.push_back(en);
	for(int i = 1; i <= n; i++) if(i != st && i != en) {
		if(hv[i][en] && hv[i][st]) continue;
		if(!hv[en][i]) continue;
		if(!vis[hv[en][i]-1]) {
			dfs(hv[en][i]-1);
		} else if(vis[hv[en][i]-1] == 2) {
			reverse(all(cur));
			while(cur.back() != en) cur.pop_back();
			cur.pop_back();
			reduce();
		}
	}
	vis[ed] = 1;
	cur.pop_back();
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	edges.resize(m);
	for(auto &[f, t] : edges) {
		cin >> f >> t;
	}
	for(int i = 0; i < m; i++) edges.push_back({edges[i][1], edges[i][0]});
	for(int i = 0; i < 2*m; i++) hv[edges[i][0]][edges[i][1]] = i+1;
	for(int i = 0; i < 2*m; i++) if(!vis[i]) {
		cur = {edges[i][0]};
		dfs(i);
	}
	cout << "no\n";
}

Compilation message (stderr)

indcyc.cpp: In lambda function:
indcyc.cpp:12:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  while(r < cur.size()) {
      |        ~~^~~~~~~~~~~~
indcyc.cpp: In function 'void reduce()':
indcyc.cpp:23:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   23 |  for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
      |  ^~~
indcyc.cpp:23:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   23 |  for(int i = l; i < r; i++) cout << cur[i] << " "; cout << endl;
      |                                                    ^~~~

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