oj.uz

Submission #82396

# Submission time Handle Problem Language Result Execution time Memory
82396 2018-10-30T12:16:34 Z aminra Potemkin cycle (CEOI15_indcyc) C++14
20 / 100
 1000 ms 34364 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int MAXN = (int)1e5+ 3;
const int infint = (int)1e9;
const ll inf = (ll)1e18;
int n, m, visited[MAXN];
set<int> G[MAXN], G2[MAXN];
vector<int> ans;
pair<int, int> cor(pair<int, int> p)
{
	return {min(p.first, p.second), max(p.first, p.second)};
}
void dfs(int u, int to)
{
	if(visited[to])
		return;
	visited[u] = 1;
	ans.push_back(u);
	for (auto v : G2[u])
		if(!visited[v])
			dfs(v, to);
	if(!visited[to])
		ans.pop_back();
}
bool check(int i, int u)
{
	set< pair<int, int> > del;
	del.insert(cor({i, u}));
	for (int j = 1; j <= n; j++)
		for (auto c : G[j])
			G2[j].insert(c);
		
	for (int j = 1; j <= n; j++)
		if(G2[i].find(j) != G2[i].end() && G2[u].find(j) != G2[u].end())
		{
			for (auto c : G2[j])
				del.insert(cor({j, c}));
		}
	for (auto pai : del)
		G2[pai.first].erase(pai.second), G2[pai.second].erase(pai.first);
	memset(visited, 0, sizeof visited);
	dfs(i, u);
	return visited[u];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		G[u].insert(v);
		G[v].insert(u);
	}
	for (int i = 1; i <= n; i++)
	{
		for (auto u : G[i])
		{
			if(check(i, u))
			{
				for (auto v : ans)
					cout << v << " ";
				return 0;
			}
		}
	}
	cout << "no";
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10104 KB Output is correct
2 Correct 11 ms 10232 KB Output is correct
3 Correct 10 ms 10232 KB Output is correct
4 Correct 10 ms 10272 KB Output is correct
5 Correct 10 ms 10272 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10312 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 10484 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 10484 KB Wrong adjacency

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 10620 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 251 ms 11036 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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