oj.uz

Submission #247046

# Submission time Handle Problem Language Result Execution time Memory
247046 2020-07-10T20:05:34 Z Sprdalo Potemkin cycle (CEOI15_indcyc) C++17
10 / 100
 1000 ms 2144 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 1010;
int n, m;
bool ok = 0;
vi e[maxn], vis(maxn);

stack<int> s;

void solve(){
	while(!s.empty()){
		cout << s.top() << ' ';
		s.pop();
	}
	cout << '\n';
	exit(0);
}

vi ud(maxn, 0);

void dfs(int x, int c, int st){


	vis[x]++;
	s.push(x);
	//cout << "USO " << x << ' ' << c << endl;

	for (auto& i : e[x]){
		if (i == st){
			if (c >= 4) solve();
			continue;
		}

		if (vis[i] || (ud[i] && c < 3)){
			++vis[i];
			continue;
		}

		++vis[i];

		dfs(i, c + 1, st);
	}

	for (auto& i : e[x])
		if (i != st)
			--vis[i];

	--vis[x];
	//cout << "IZASO " << x << '\n';
	s.pop();
}

void init(){
	for (int i = 1; i <= n; ++i){
		vis[i] = 0;
	}
	while(!s.empty()) s.pop();
}

signed main()
{
	ios_base::sync_with_stdio(false); 
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	cerr.tie(nullptr);	

	cin >> n >> m;

	for (int i = 0; i < m; ++i){
		int u, v;
		cin >> u >> v;

		e[u].push_back(v);
		e[v].push_back(u);
	}

	for (int i = 1; i <= n; ++i){
		init();
		//if (i != 2) continue;
		s.push(i);
		for (auto& j : e[i])
			ud[j] = 1;
		for (auto& j : e[i]){
			dfs(j,2,i);
		}
	}

	cout << "no\n";
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong adjacency

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Wrong adjacency

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 384 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1280 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 611 ms 2144 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -