oj.uz

Submission #244436

# Submission time Handle Problem Language Result Execution time Memory
244436 2020-07-04T05:49:29 Z shenxy Potemkin cycle (CEOI15_indcyc) C++11
20 / 100
 26 ms 2048 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> ii;
int N, R, depth[1000], parent[1000];
bool visited[1000];
vector<int> adjlist[1000];
ii ans = ii(-1, -1);
void dfs(int v, int jmp_h) {
	visited[v] = true;
	int max_h = -1, good_i = -1;
	for (int i: adjlist[v]) {
		if (i == parent[v] || !visited[i]) continue;
		if (depth[v] - depth[i] > 2 && depth[i] > max_h) {
			max_h = depth[i];
			good_i = i;
		}
		jmp_h = max(depth[i], jmp_h);
	}
	if (depth[v] - max_h > 2 && max_h >= jmp_h) ans = ii(good_i, v);
	for (int i: adjlist[v]) {
		if (visited[i]) continue;
		depth[i] = depth[v] + 1;
		parent[i] = v;
		dfs(i, jmp_h);
	}
}
int main() {
	scanf("%d %d", &N, &R);
	int u, v;
	for (int i = 0; i < R; ++i) {
		scanf("%d %d", &u, &v);
		adjlist[u - 1].push_back(v - 1);
		adjlist[v - 1].push_back(u - 1);
	}
	fill_n(visited, N, false);
	for (int i = 0; i < N; ++i) {
		if (!visited[i]) {
			depth[i] = 0;
			parent[i] = -1;
			dfs(i, -1);
		}
	}
	if (ans != ii(-1, -1)) {
		for (int i = ans.second; i != parent[ans.first]; i = parent[i]) printf("%d ", i + 1);
	} else printf("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &R);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong adjacency

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1280 KB Output is correct
2 Correct 25 ms 2048 KB Output is correct
3 Incorrect 19 ms 1536 KB Wrong adjacency
4 Halted 0 ms 0 KB -