Submission #24672

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
24672	2017-06-10T21:12:55 Z	Bruteforceman	Potemkin cycle (CEOI15_indcyc)	C++11	70 / 100	1000 ms	8328 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) { 
	for(int i = 0; i < m; i++) {
		if(bad[l[i]] && bad[r[i]]) continue;
		if(l[i] == c || r[i] == c || l[i] == b || r[i] == b) {
			del[i] = false;
		} 
	}
	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;
	for(auto i : g[x]) {
		int y = l[i] ^ r[i] ^ x;
		if(bad[y] == true) {
			bad_nodes.push_back(y);
		}
		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]) {
		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[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:111: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:114: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
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	6336 KB	Output is correct
2	Correct	0 ms	6336 KB	Output is correct
3	Correct	16 ms	6332 KB	Output is correct
4	Correct	506 ms	6328 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	6332 KB	Output is correct
2	Correct	336 ms	6332 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	7304 KB	Output is correct
2	Correct	9 ms	6912 KB	Output is correct
3	Execution timed out	1000 ms	7436 KB	Execution timed out
4	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	6852 KB	Execution timed out
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	39 ms	8328 KB	Output is correct
2	Correct	69 ms	8316 KB	Output is correct
3	Execution timed out	1000 ms	7788 KB	Execution timed out
4	Halted	0 ms	0 KB	-