oj.uz

답안 #24672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
24672 2017-06-10T21:12:55 Z Bruteforceman Potemkin cycle (CEOI15_indcyc) C++11
70 / 100
 1000 ms 8328 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6192 KB Output is correct
2 Correct 0 ms 6192 KB Output is correct
3 Correct 0 ms 6192 KB Output is correct
4 Correct 0 ms 6192 KB Output is correct
5 Correct 0 ms 6192 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6192 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6192 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 6852 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 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 -