oj.uz

Submission #244485

# Submission time Handle Problem Language Result Execution time Memory
244485 2020-07-04T07:12:30 Z shenxy Potemkin cycle (CEOI15_indcyc) C++11
20 / 100
 28 ms 2168 KB 
//happy birthday errorgorn
#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, rmax_h = jmp_h;
	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;
		}
		rmax_h = max(depth[i], rmax_h);
	}
	if (max_h == rmax_h && 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, rmax_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.first != -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:31: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:34: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 5 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 Expected integer, but "no" found

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 6 ms 512 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 768 KB Expected integer, but "no" found
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 28 ms 2168 KB Output is correct
3 Incorrect 22 ms 1536 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -