Submission #24659

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24659	2017-06-10T20:29:19 Z	Bruteforceman	Potemkin cycle (CEOI15_indcyc)	C++11	30 / 100	79 ms	8320 KB

indcyc

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

int n, m;
vector <int> g[1005];
bool vis[1005];
int par[1005];

vector <int> l, r;
bool del[100010];
bool bad[100010];

int mat[1005][1005];

vector <int> path (int c, int b) { 
	memset(vis, false, sizeof vis);
	memset(par, false, sizeof par);
	queue <int> q;
	q.push(b);
	vis[b] = true;
	par[b] = -1;
	while(not q.empty()) {
		int x = q.front();
		q.pop();
		for(int i : g[x]) {
			int y = l[i] ^ r[i] ^ x;
			if(vis[y] == false && del[i] == false) {
				par[y] = x;
				vis[y] = true;
				q.push(y);
			}
		}
	} 
	vector <int> ans;
	int cur = c;
	while(cur != -1) {
		ans.push_back(cur);
		cur = par[cur];
	}
	return ans;
}

vector <int> bad_nodes;

void dfs(int x) {
	vis[x] = true;
	if(bad[x]) {
		bad_nodes.push_back(x);
	}
	for(auto i : g[x]) {
		int y = l[i] ^ r[i] ^ x;
		if(vis[y] == false && del[i] == false) {
			dfs(y);
		} 
	}
}

void check(int root) {
	memset(vis, false, sizeof vis);
	memset(del, false, sizeof del);
	memset(bad, false, sizeof bad);

	bad[root] = true;
	for(auto i : g[root]) {
		del[i] = true;
		bad[l[i] ^ r[i] ^ root] = true;
	}
	for(int i = 0; i < m; i++) {
		if(bad[l[i]] && bad[r[i]]) {
			del[i] = true;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(vis[i] == false) {
			bad_nodes.clear();
			dfs(i);
			
			bool good = false;
			int p = -1;
			int q = -1;
			for(auto j : bad_nodes) {
				for(auto k : bad_nodes) {
					if(mat[j][k] == 0 && k != j) {
						p = j;
						q = k;
						good = true;
						goto here;
					}
				}
			}
			here:
			if(good) {
				vector <int> ans = path(p, q);
				for(auto j : ans) {
					printf("%d ", j);
				}
				printf("%d\n", root);
				exit(0);
			}
		}
	}
}

int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int p, q;
		scanf("%d %d", &p, &q);
		g[p].push_back(i);
		g[q].push_back(i);
		l.push_back(p);
		r.push_back(q);
		mat[p][q] = mat[q][p] = 1;
	} 
	for(int i = 1; i <= n; i++) {
		check(i);
	}
	printf("no\n");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main(int, const char**)':
indcyc.cpp:106:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
indcyc.cpp:109:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &p, &q);
                         ^

Subtask #1
10.0 / 10.0

#	Verdict	Memory	Grader output
1	Correct	6192 KB	Output is correct
2	Correct	6192 KB	Output is correct
3	Correct	6192 KB	Output is correct
4	Correct	6192 KB	Output is correct
5	Correct	6192 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	6192 KB	Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	6192 KB	Output is correct

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	6192 KB	Wrong adjacency
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	6336 KB	Output is correct
2	Correct	0 ms	6336 KB	Output is correct
3	Incorrect	3 ms	6332 KB	Wrong adjacency
4	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	6332 KB	Wrong adjacency
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	7304 KB	Output is correct
2	Incorrect	13 ms	6912 KB	Wrong adjacency
3	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	9 ms	6852 KB	Wrong adjacency
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	79 ms	8320 KB	Wrong adjacency
2	Halted	0 ms	0 KB	-