oj.uz

Submission #25158

# Submission time Handle Problem Language Result Execution time Memory
25158 2017-06-20T10:10:16 Z kajebiii Potemkin cycle (CEOI15_indcyc) C++14
50 / 100
 1000 ms 10960 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]==0?v:UNF[v]=F(UNF[v]);
}
void U(int a, int b) {
	a = F(a); b = F(b);
	if(a == b) return;
	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);
//	printf("%d %d %d\n", r, x, y);

	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);
}

int Vis[MAX_N][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++) {
		memset(UNF, 0, sizeof(UNF));
//		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);

		vector<int> Gp[MAX_N];
		for(int i=1; i<=N; i++) if(ChkV[i] != v)
			for(int x : Ed[i]) if(ChkV[x] == v && x != v && Vis[F(i)][x] != v) {
				Gp[F(i)].push_back(x);
				Vis[F(i)][x] = v;
			}
		
		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:65: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 10036 KB Output is correct
2 Correct 0 ms 10036 KB Output is correct
3 Correct 0 ms 10036 KB Output is correct
4 Correct 0 ms 10036 KB Output is correct
5 Correct 0 ms 10036 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 10036 KB Output is correct
2 Correct 3 ms 10036 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10168 KB Output is correct
2 Correct 0 ms 10168 KB Output is correct
3 Correct 3 ms 10168 KB Output is correct
4 Correct 39 ms 10168 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10960 KB Output is correct
2 Correct 46 ms 10960 KB Output is correct
3 Correct 56 ms 10828 KB Output is correct
4 Execution timed out 1000 ms 10828 KB Execution timed out