oj.uz

Submission #25149

# Submission time Handle Problem Language Result Execution time Memory
25149 2017-06-20T08:25:34 Z 김종범(#1056) Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 39 ms 6976 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, D[MAX_N][MAX_N];
vector<int> Ed[MAX_N];

int ChkV[MAX_N], UNF[MAX_N], Val[MAX_N];
int F(int v) {return UNF[v]==v?v:UNF[v]=F(UNF[v]);}
void U(int a, int b) {
	a = F(a); b = F(b);
	if(rand()%2) UNF[a] = b; else UNF[b] = a;
}
int P[MAX_N];
void findPath(int r, int x, int y) {
	vector<bool> vis(N+1, false);

	queue<int> Q; Q.push(x); vis[x] = true;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		for(int w : Ed[v]) {
			if(vis[w]) continue;
			if(v == x && w == y) continue;
			if(w == y) {
				Q.push(w); P[w] = v;
				break;
			} else {
				if(ChkV[w] == r) continue;
				vis[w] = true;
				Q.push(w); P[w] = v;
			}
		}
	}

	int now = y;
	while(true) {
		printf("%d ", now);
		if(now == x) break;
		now = P[now];
	}
	printf("%d\n", r);
}
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);
		D[x][y] = D[y][x] = 1;
	}

	for(int v=1; v<=N; v++) {
		for(int i=1; i<=N; i++) UNF[i] = i;

		for(int w : Ed[v]) ChkV[w] = v; ChkV[v] = v;
		for(int x=1; x<=N; x++) if(ChkV[x] != v) 
			for(int y : Ed[x]) if(ChkV[y] != v)
				U(x, y);

		for(int i=1; i<=N; i++) Val[i] = 0;

		for(int x=1; x<=N; x++) if(ChkV[x] != v)
			for(int y : Ed[x]) if(ChkV[y] == v && y != v) {
				if(Val[F(x)] == 0) Val[F(x)] = y;
				else {
					if(D[Val[F(x)]][y] == 1) continue;
					findPath(v, Val[F(x)], y);
					return 0;
				}
			}
	}
	puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:60: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6052 KB Output is correct
2 Incorrect 0 ms 6052 KB Wrong answer on graph without induced cycle
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6052 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6052 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 6184 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 Correct 3 ms 6052 KB Too short sequence
2 Incorrect 0 ms 6052 KB Wrong answer on graph without induced cycle

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6580 KB Too short sequence
2 Correct 6 ms 6448 KB Too short sequence
3 Incorrect 19 ms 6580 KB Wrong answer on graph without induced cycle
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6976 KB Too short sequence
2 Correct 23 ms 6976 KB Output is correct
3 Correct 29 ms 6844 KB Too short sequence
4 Incorrect 39 ms 6844 KB Wrong answer on graph without induced cycle