Submission #154522

#	Time	Username	Problem	Language	Result	Execution time	Memory
154522		Mamnoon_Siam	Potemkin cycle (CEOI15_indcyc)	C++17	40 / 100	384 ms	6136 KiB

indcyc

#include  <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 1;
const int maxm = 1e5 + 1;

int N, M;
int l[maxm], r[maxm];
vector<int> vl[maxn], el[maxn];
int par[maxn], sz[maxn];
int lvl[maxn], prv[maxn];
int g[maxn][maxn];
int dont[maxn];

inline int find(int u) {
	return par[u] == u ? u : par[u] = find(par[u]);
}
void unite(int u, int v) {
	u = find(u), v = find(v);
	if(u != v) {
		if(sz[u] > sz[v]) swap(u, v);
		sz[v] += sz[u], par[u] = v;
	}
}

vector<int> solve(int center) {
	memset(dont, 0, sizeof dont);
	for(int u : vl[center]) dont[u] = 1;
	dont[center] = 1;
	for(int i = 0; i < N; i++) {
		par[i] = i, sz[i] = 1;
	}
	for(int i = 0; i < M; i++) {
		if(!dont[l[i]] or !dont[r[i]]) {
			unite(l[i], r[i]);
		}
	}
	int x = -1, y = -1;
	for(int i = 0; i < vl[center].size(); i++) {
		int u = vl[center][i];
		for(int j = i + 1; j < vl[center].size(); j++) {
			int v = vl[center][j];
			if(!g[u][v] and find(u) == find(v)) {
				x = u, y = v;
			}
		}
	}
	if(x == -1) {
		return vector<int>();
	}
	for(int i = 0; i < N; i++) {
		lvl[i] = 100000;
		prv[i] = -1;
	}
	dont[x] = dont[y] = 0;
	queue<int> Q;
	Q.push(x);
	lvl[x] = 0;
	while(Q.size()) {
		int u = Q.front();
		Q.pop();
		for(int v : vl[u]) if(!dont[v]) {
			if(lvl[v] == 100000) {
				lvl[v] = lvl[u] + 1;
				prv[v] = u;
				Q.push(v);
				if(v == y)
					goto stop_bfs;
			}
		}
	}
	stop_bfs : ;
	int cur = y;
	vector<int> cyc;
	while(cur != -1) {
		cyc.emplace_back(cur);
		cur = prv[cur];
	} return cyc;
}

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	scanf("%d %d", &N, &M);
	for(int i = 0; i < M; i++) {
		scanf("%d %d", &l[i], &r[i]);
		l[i]--, r[i]--;
		g[l[i]][r[i]] = g[r[i]][l[i]] = 1;
		vl[l[i]].emplace_back(r[i]);
		vl[r[i]].emplace_back(l[i]);
	}
	for(int i = 0; i < N; i++) {
		vector<int> cyc = solve(i);
		if(cyc.size()) {
			printf("%d ", i + 1);
			for(int x : cyc) printf("%d ", x + 1);
			putchar('\n');
			exit(0);
		}
	}
	puts("no");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'std::vector<int> solve(int)':
indcyc.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < vl[center].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
indcyc.cpp:41:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < vl[center].size(); j++) {
                      ~~^~~~~~~~~~~~~~~~~~~
indcyc.cpp: In function 'int main(int, const char**)':
indcyc.cpp:84:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l[i], &r[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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