oj.uz

Submission #50096

# Submission time Handle Problem Language Result Execution time Memory
50096 2018-06-07T14:03:23 Z radoslav11 Potemkin cycle (CEOI15_indcyc) C++14
60 / 100
 1000 ms 3204 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]; 
	}
};

bool rhas[MAXN];
bool used[MAXN];
bool ok[MAXN][MAXN];

void dfs(int u, int rt)
{
	used[u] = 1;
	for(int v: adj[u])
		if(!used[v] && !rhas[v])
			dfs(v, rt);
		else if(rhas[v])
			ok[rt][v] = 1;
}

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++)
	{
		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 v: adj[root])
			for(int u: adj[root])
				ok[u][v] = 0;

		for(int v: adj[root]) dfs(v, v);		

		for(int v: adj[root])
			for(int u: adj[root])
				if(v < u && !has[u][v] && (ok[u][v] || ok[v][u]))
					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 380 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 2 ms 452 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 548 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1248 KB Output is correct
2 Correct 4 ms 1248 KB Output is correct
3 Correct 5 ms 1248 KB Output is correct
4 Correct 24 ms 1388 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3180 KB Output is correct
2 Correct 18 ms 3180 KB Output is correct
3 Correct 381 ms 3204 KB Output is correct
4 Correct 180 ms 3204 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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