oj.uz

Submission #25138

# Submission time Handle Problem Language Result Execution time Memory
25138 2017-06-20T08:04:38 Z 김현수(#1051) Potemkin cycle (CEOI15_indcyc) C++11
20 / 100
 1000 ms 789548 KB 
#include<bits/stdc++.h>
using namespace std;
int n, m, pos[1005], ep;
bool vis[1005], can[1005][1005], av;
vector<int> adj[1005], cyc, rl;

bool solve (int C, int P) {
	vis[C] = true;
	for(auto &N : adj[C]) {
		if(N == P || can[P][N]) continue;
		if(vis[N] || solve(N, C)) {
			if(!ep) {ep = N; av = true;}
			if(av) {
				cyc.push_back(C);
				pos[C] = cyc.size();
			}
			if(ep == C) av = false;
			return true;
		}
	}
	return false;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		adj[A].push_back(B);
		can[A][B] = true;
		adj[B].push_back(A);
		can[B][A] = true;
	}
	for(int i=1;i<=n;i++) {
		for(auto &T : adj[i]) {
			vis[i] = true;
			if(solve(T, i)) {
				if(ep == i) cyc.push_back(i);
				break;
			}
			for(int j=1;j<=n;j++) vis[j] = false;
		}
		if(!cyc.empty()) break;
	}
	if(cyc.empty()) {puts("no"); return 0;}
	rl.push_back(cyc[0]);
	for(int i=1;i<cyc.size();) {
		rl.push_back(cyc[i]);
		if(i != 1 && can[cyc[i]][cyc[0]]) break;
		int mx = 0;
		for(auto &T : adj[cyc[i]]) {
			mx = max(mx, pos[T]);
		}
		i = mx-1;
	}
	for(auto &T : rl) printf("%d ",T);
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<cyc.size();) {
               ^
indcyc.cpp:26:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
indcyc.cpp:29:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
                      ^

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3032 KB Output is correct
2 Execution timed out 1000 ms 789548 KB Execution timed out

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 199744 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 396384 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 396380 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 200264 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 52540 KB Execution timed out
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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