Submission #244431

#	Time	Username	Problem	Language	Result	Execution time	Memory
244431		shenxy	Potemkin cycle (CEOI15_indcyc)	C++11	20 / 100	24 ms	1280 KiB

indcyc

#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 = -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;
		}
		rmax_h = max(depth[i], rmax_h);
	}
	if (depth[v] - max_h > 2 && max_h > jmp_h) ans = ii(good_i, v);
	jmp_h = max(jmp_h, rmax_h);
	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 (stderr)

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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10