oj.uz

Submission #25105

# Submission time Handle Problem Language Result Execution time Memory
25105 2017-06-20T06:58:58 Z 김종범(#1056) Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 23 ms 2984 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], reIx[MAX_N];
void dfs(int v, int p) {
	P[v] = p;
	Ix[v] = ++IN;
	reIx[IN] = v;

	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;
		maxV = reIx[maxV];
		int now = v, cnt = 1;
		bool isCan = true;
		while(true) {
			now = P[now];
			cnt++;
			if(now == maxV) break;
			if(reIx[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:44: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 2060 KB Output is correct
2 Correct 0 ms 2060 KB Output is correct
3 Correct 0 ms 2060 KB Output is correct
4 Correct 0 ms 2060 KB Output is correct
5 Correct 0 ms 2060 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 KB Wrong adjacency

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 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 0 ms 2060 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2060 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 0 ms 2192 KB Output is correct
2 Incorrect 0 ms 2192 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 0 ms 2060 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 13 ms 2588 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 3 ms 2324 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 23 ms 2984 KB Output is correct
2 Correct 19 ms 2984 KB Output is correct
3 Incorrect 13 ms 2852 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -