oj.uz

Submission #50040

# Submission time Handle Problem Language Result Execution time Memory
50040 2018-06-06T19:58:24 Z radoslav11 Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 39 ms 26220 KB 
#include <bits/stdc++.h>
#define endl '\n'

//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

int n, m, disc[MAXN], low[MAXN], dfs_time;
vector<int> adj[MAXN];

void read()
{
	cin >> n >> m;
	for(int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

int par[MAXN], dep[MAXN], ver[MAXN];

void tarjan(int u, int pr = -1)
{
	disc[u] = ++dfs_time;
	ver[dfs_time] = u;
	low[u] = pr == -1 ? 0 : low[pr];
	dep[u] = pr == -1 ? 0 : (dep[pr] + 1);

	int closest = 0;
	for(int v: adj[u])
		if(v != pr && disc[v])
			chkmax(closest, disc[v]);

	for(int v: adj[u])
		if(v != pr && disc[v] > low[u] && closest == disc[v] && dep[u] - dep[v] >= 3)
		{
			int x = u;
			while(x != v)
			{
				cout << x << " ";
				x = par[x];
			}

			cout << v << endl;
			exit(0);
		}

	chkmax(low[u], closest);
	for(int v: adj[u])
		if(v != pr && !disc[v])
		{
			par[v] = u;
			tarjan(v, u);


		}
}

void solve()
{
	for(int i = 1; i <= n; i++)
		if(!disc[i]) tarjan(i);

	cout << "no" << endl; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	read();
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24952 KB Output is correct
2 Correct 23 ms 25064 KB Output is correct
3 Correct 24 ms 25232 KB Output is correct
4 Correct 21 ms 25232 KB Output is correct
5 Correct 23 ms 25232 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 25232 KB Expected integer, but "no" found

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 25276 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 25300 KB Output is correct
2 Incorrect 23 ms 25364 KB Expected integer, but "no" found
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 26168 KB Output is correct
2 Correct 39 ms 26220 KB Output is correct
3 Incorrect 36 ms 26220 KB Expected integer, but "no" found
4 Halted 0 ms 0 KB -