oj.uz

Submission #73693

# Submission time Handle Problem Language Result Execution time Memory
73693 2018-08-28T17:41:26 Z arman_ferdous Potemkin cycle (CEOI15_indcyc) C++17
70 / 100
 1000 ms 6488 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
vector<int> g[N];

int n, m, par[N];
int bfs(int s, int t, int del) {
	par[s] = del;
	par[del] = 0;

	queue<int> q; q.push(s);
	while(!q.empty()) {
		int u = q.front(); q.pop();
		for(int v : g[u]) if(par[v] == -1) {
			par[v] = u; q.push(v);
		}
	} return par[t] != -1;
}

vector<int> soln;
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++) {
		int u, v; scanf("%d %d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int u = 1; u <= n; u++)
		sort(g[u].begin(),g[u].end());

	for(int x = 1; x <= n; x++) {
		for(int u : g[x]) for(int v : g[x]) {
			if(u != v && binary_search(g[u].begin(),g[u].end(),v) == false) {
				fill(par,par+n+1,-1);
				for(int i : g[x]) if(i != v && i != u) par[i] = 0;
				if(bfs(u,v,x)) {
					int cur = v;
					while(par[cur]) {
						soln.push_back(cur);
						cur = par[cur];
					} soln.push_back(cur);
					int sz = soln.size();
					for(int i = sz - 1; i >= 0; i--)
						printf("%d ", soln[i]);
					return 0;
				}
			}
		}
	} puts("no");
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:25:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d %d", &u, &v);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2740 KB Output is correct
3 Correct 4 ms 2740 KB Output is correct
4 Correct 5 ms 2908 KB Output is correct
5 Correct 4 ms 2944 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2944 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3012 KB Output is correct
2 Correct 4 ms 3036 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3036 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3128 KB Output is correct
2 Correct 23 ms 3128 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3216 KB Output is correct
2 Correct 6 ms 3256 KB Output is correct
3 Correct 6 ms 3300 KB Output is correct
4 Correct 299 ms 3484 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3484 KB Output is correct
2 Correct 245 ms 3484 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 4216 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4216 KB Output is correct
2 Execution timed out 1068 ms 4292 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5780 KB Output is correct
2 Execution timed out 1071 ms 6488 KB Time limit exceeded
3 Halted 0 ms 0 KB -