oj.uz

Submission #154522

# Submission time Handle Problem Language Result Execution time Memory
154522 2019-09-22T12:31:46 Z Mamnoon_Siam Potemkin cycle (CEOI15_indcyc) C++17
40 / 100
 384 ms 6136 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 3 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 2 ms 504 KB Wrong answer on graph without induced cycle

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Incorrect 3 ms 888 KB Wrong answer on graph without induced cycle

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1656 KB Output is correct
2 Correct 5 ms 1708 KB Output is correct
3 Correct 5 ms 1656 KB Too short sequence
4 Incorrect 5 ms 1784 KB Wrong answer on graph without induced cycle

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1748 KB Too short sequence
2 Incorrect 4 ms 1656 KB Wrong answer on graph without induced cycle

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 5604 KB Too short sequence
2 Correct 13 ms 4856 KB Output is correct
3 Correct 384 ms 5628 KB Output is correct
4 Correct 173 ms 5112 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4856 KB Too short sequence
2 Incorrect 12 ms 4856 KB Wrong answer on graph without induced cycle

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 4472 KB Output is correct
2 Correct 163 ms 4592 KB Output is correct
3 Correct 25 ms 6008 KB Too short sequence
4 Incorrect 25 ms 6136 KB Wrong answer on graph without induced cycle