oj.uz

Submission #50095

# Submission time Handle Problem Language Result Execution time Memory
50095 2018-06-07T13:58:38 Z radoslav11 Potemkin cycle (CEOI15_indcyc) C++14
70 / 100
 1000 ms 2572 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 << 10);

int n, m;
vector<int> adj[MAXN];
bool has[MAXN][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);
	
		has[u][v] = 1;
		has[v][u] = 1;
	}
}

struct dsu
{
	int sz;
	vector<int> par, psz;

	void init(int n)
	{
		sz = n;
		par.assign(sz + 1, 0);
		psz.assign(sz + 1, 0);
		for(int i = 0; i <= sz; i++)
			par[i] = i, psz[i] = 1;
	}

	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
	
	bool connected(int x, int y) { return root(x) == root(y); }

	void unite(int x, int y)
	{
		x = root(x), y = root(y);
		if(x == y) return;
		if(psz[x] > psz[y]) swap(x, y);
		par[x] = y, psz[y] += psz[x]; 
	}
};

dsu d;
bool used[MAXN];

void dfs(int u)
{
	used[u] = 1;
	for(int v: adj[u])
		if(!used[v])
		{
			dfs(v);
			d.unite(u, v);
		}
}

bool rhas[MAXN];
int par[MAXN];

void solve(int rt, int l, int r)
{
	queue<int> q;
	memset(par, -1, sizeof(par));
	
	q.push(l);
	par[l] = rt;
	par[rt] = 0;
	
	while(!q.empty())
	{
		int u = q.front();
		q.pop();

		for(int v: adj[u])
			if(par[v] == -1 && (!rhas[v] || v == r))
			{
				q.push(v);
				par[v] = u;
			}
	}

	if(par[r] == -1) return;

	int x = r;
	while(x)
	{
		cout << x << " ";
		x = par[x];
	}

	cout << endl;
	exit(0);
}

void solve()
{
	for(int root = 1; root <= n; root++)
	{
		d.init(n);
		for(int i = 1; i <= n; i++) used[i] = 0, rhas[i] = 0;

		used[root] = 1;
		for(int v: adj[root])
			rhas[v] = 1, dfs(v);		

		for(int v: adj[root])
			for(int u: adj[root])
				if(v < u && !has[u][v] && d.root(u) == d.root(v))
					solve(root, u, v);
	}

	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 2 ms 376 KB Output is correct
2 Correct 2 ms 420 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 628 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 2 ms 628 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 692 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 736 KB Output is correct
2 Correct 11 ms 864 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 1044 KB Output is correct
2 Correct 3 ms 1044 KB Output is correct
3 Correct 4 ms 1044 KB Output is correct
4 Correct 89 ms 1044 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1044 KB Output is correct
2 Correct 151 ms 1044 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 2240 KB Output is correct
2 Correct 92 ms 2240 KB Output is correct
3 Execution timed out 1084 ms 2284 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 2284 KB Output is correct
2 Execution timed out 1078 ms 2284 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2284 KB Output is correct
2 Correct 510 ms 2284 KB Output is correct
3 Correct 147 ms 2572 KB Output is correct
4 Execution timed out 1077 ms 2572 KB Time limit exceeded