oj.uz

Submission #25099

# Submission time Handle Problem Language Result Execution time Memory
25099 2017-06-20T06:50:46 Z 김종범(#1056) Potemkin cycle (CEOI15_indcyc) C++14
10 / 100
 1000 ms 2980 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e3 + 10;

int N, M;
vector<int> Ed[MAX_N];

int Ix[MAX_N], IN, P[MAX_N], firstIx[MAX_N];
void dfs(int v, int p) {
	P[v] = p;
	Ix[v] = ++IN;

	int maxV = -1;
	for(int w : Ed[v]) {
		if(Ix[w] == 0) {
			dfs(w, v);
		} else {
			if(w == p) continue;
			if(Ix[w] > Ix[v]) continue;
			maxV = max(maxV, Ix[w]);
		}
	}
	firstIx[v] = maxV;
	return;
}
int main() {
	cin >> N >> M;
	while(M--) {
		int x, y;
		scanf("%d%d", &x, &y);
		Ed[x].push_back(y); Ed[y].push_back(x);
	}
	dfs(1, 0);

	bool findAns = false;
	for(int v=1; v<=N; v++) {
		int maxV = firstIx[v];
		if(maxV == -1) continue;
		int now = v, cnt = 1;
		bool isCan = true;
		while(true) {
			now = P[now];
			cnt++;
			if(now == maxV) break;
			if(firstIx[now] >= maxV) {
				isCan = false;
				break;
			}
		}
		if(isCan && cnt >= 4) {
			now = v;
			printf("%d ", now);
			while(true) {
				now = P[now];
				printf("%d ", now);
				if(now == maxV) break;
			}
			puts("");
			findAns = true;
			break;
		}
	}
	if(!findAns) puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:43: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 0 ms 2056 KB Output is correct
2 Correct 0 ms 2056 KB Output is correct
3 Correct 0 ms 2056 KB Output is correct
4 Correct 0 ms 2056 KB Output is correct
5 Correct 0 ms 2056 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2056 KB Execution timed out

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 2056 KB Execution timed out

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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