oj.uz

Submission #50102

# Submission time Handle Problem Language Result Execution time Memory
50102 2018-06-07T14:22:24 Z radoslav11 Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 394 ms 2508 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];
bool rhas[MAXN];
 
void dfs(int u)
{
	used[u] = 1;
	if(rhas[u]) return;
	for(int v: adj[u])
		if(!used[v])
		{
			dfs(v);
			d.unite(u, v);
		}
}
 
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;
		
		for(int i = 1; i <= n; i++)
			if(!used[i]) dfs(i);		
 
		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 376 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 568 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1000 KB Output is correct
2 Correct 4 ms 1000 KB Output is correct
3 Correct 4 ms 1004 KB Output is correct
4 Correct 17 ms 1076 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2300 KB Output is correct
2 Correct 21 ms 2300 KB Output is correct
3 Correct 278 ms 2300 KB Output is correct
4 Correct 138 ms 2300 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 2300 KB Output is correct
2 Correct 168 ms 2300 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2300 KB Output is correct
2 Correct 340 ms 2300 KB Output is correct
3 Correct 32 ms 2424 KB Output is correct
4 Correct 394 ms 2508 KB Output is correct