oj.uz

Submission #95113

# Submission time Handle Problem Language Result Execution time Memory
95113 2019-01-27T11:52:51 Z MrTEK Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 300 ms 2780 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;
			}
	}
  
	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 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 760 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 4 ms 760 KB Output is correct
4 Correct 11 ms 760 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2296 KB Output is correct
2 Correct 12 ms 1912 KB Output is correct
3 Correct 225 ms 2424 KB Output is correct
4 Correct 103 ms 2040 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1784 KB Output is correct
2 Correct 120 ms 1860 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2552 KB Output is correct
2 Correct 257 ms 2424 KB Output is correct
3 Correct 21 ms 2612 KB Output is correct
4 Correct 300 ms 2780 KB Output is correct