oj.uz

Submission #25135

# Submission time Handle Problem Language Result Execution time Memory
25135 2017-06-20T07:59:10 Z 김동현(#1052) Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 1000 ms 189696 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m, a[1010][1010], vis[1010], ins[1010], nx[1010], fl;
vector<int> e[1010], v[1010][1010];
stack<int> st;

int fnd(int x, int y, int z){
	int t[3] = {x, y, z};
	sort(t, t + 3);
	auto u = lower_bound(v[t[0]][t[1]].begin(), v[t[0]][t[1]].end(), t[2]);
	if(u != v[t[0]][t[1]].end() && *u == t[2]) return 1;
	return 0;
}

void f(int x, int p){
	if(fl) return;
	vis[x] = 1;
	st.push(x);
	ins[x] = 1;
	for(auto &i : e[x]){
		if(i == p) continue;
		if(ins[i]){
			if(fnd(p, x, i)) continue;
			if(fnd(x, i, nx[i])) continue;
			while(st.top() != i){
				printf("%d ", st.top());
				st.pop();
			}
			printf("%d\n", i);
			fl = 1;
			return;
		}
		if(vis[i]) continue;
		nx[x] = i;
		f(i, x);
		if(fl) return;
	}
	ins[x] = 0;
	st.pop();
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0, x, y; i < m; i++){
		scanf("%d%d", &x, &y);
		a[x][y] = a[y][x] = 1;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < e[i].size(); j++){
			for(int k = j + 1; k < e[i].size(); k++){
				if(a[e[i][j]][e[i][k]]){
					int t[3] = {i, e[i][j], e[i][k]};
					sort(t, t + 3);
					v[t[0]][t[1]].push_back(t[2]);
				}
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = i + 1; j <= n; j++){
			sort(v[i][j].begin(), v[i][j].end());
		}
	}
	f(1, 0);
	if(!fl) puts("no");
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:52:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < e[i].size(); j++){
                    ^
indcyc.cpp:53:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k = j + 1; k < e[i].size(); k++){
                         ^
indcyc.cpp:44:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
indcyc.cpp:46:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29956 KB Output is correct
2 Correct 3 ms 29956 KB Output is correct
3 Correct 3 ms 29956 KB Output is correct
4 Correct 6 ms 29956 KB Output is correct
5 Correct 6 ms 29956 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 29956 KB Wrong adjacency

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29956 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 33784 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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