oj.uz

Submission #25154

# Submission time Handle Problem Language Result Execution time Memory
25154 2017-06-20T09:54:12 Z kajebiii Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 49 ms 7144 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; vis[r] = true;
	while(!Q.empty()) {
		int v = Q.front(); Q.pop();
		for(int w : Ed[v]) {
			if(vis[w]) 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);
}

vector<int> Gp[MAX_N];
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++) Gp[i].clear(), Gp[i].shrink_to_fit();
		for(int i=1; i<=N; i++) if(ChkV[i] != v)
			for(int x : Ed[i]) if(ChkV[x] == v && x != v) {
				Gp[F(i)].push_back(x);
			}
		
		for(int i=1; i<=N; i++) 
			if(SZ(Gp[i]) >= 2) {
//				for(int x : Gp[i]) printf("%d ", x); puts("");
				for(int x=0; x<SZ(Gp[i]); x++) for(int y=x+1; y<SZ(Gp[i]); y++) {
					int a = Gp[i][x], b = Gp[i][y];
					if(D[a][b] == 0) {
						findPath(v, a, b);
						return 0;
					}
				}
			}
	}
	puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:61: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 6076 KB Output is correct
2 Incorrect 0 ms 6076 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 6076 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6604 KB Too short sequence
2 Correct 16 ms 6472 KB Too short sequence
3 Incorrect 23 ms 6604 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 6 ms 6488 KB Too short sequence
2 Incorrect 6 ms 6488 KB Wrong answer on graph without induced cycle

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 7144 KB Too short sequence
2 Correct 33 ms 7000 KB Output is correct
3 Correct 26 ms 6868 KB Too short sequence
4 Incorrect 26 ms 7032 KB Wrong answer on graph without induced cycle