oj.uz

Submission #702187

# Submission time Handle Problem Language Result Execution time Memory
702187 2023-02-23T07:57:19 Z ajab_01 Potemkin cycle (CEOI15_indcyc) C++17
100 / 100
 145 ms 5584 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 3;
const int INF = 1e9;
vector<int> g[N] , comp[N] , ans;
int mat[N][N] , mark[N] , vis[N] , par[N] , dis[N] , n , m;
deque<int> dq;

void clr(){
	for(int u = 1 ; u <= n ; u++){
		comp[u].clear();
		par[u] = u;
		mark[u] = vis[u] = 0;
	}
}

int get(int u){
	if(u == par[u]) return u;
	par[u] = get(par[u]);
	return par[u];
}

void merge(int u , int v){
	u = get(u);
	v = get(v);
	if(u == v)
		return;
	if(comp[u].size() < comp[v].size())
		swap(u , v);
	par[v] = u;
	for(int w : comp[v])
		comp[u].push_back(w);
}

void dfs(int v){
	vis[v] = 1;
	if(mark[v]) return;
	for(int u : g[v]){
		if(vis[u]) continue;
		merge(u , v);
		dfs(u);
	}
}

void cal(int v , int u , int w){
	for(int i = 1 ; i <= n ; i++)
		dis[i] = INF;
	mark[v] = mark[w] = 0;
	dq.push_back(v);
	dis[v] = 0;
	while(!dq.empty()){
		int i = dq.front();
		dq.pop_front();
		for(int j : g[i]){
			if(mark[j] || dis[j] <= dis[i] + 1)
				continue;
			dis[j] = dis[i] + 1;
			dq.push_back(j);
			par[j] = i;
		}
	}
	ans.push_back(v);
	ans.push_back(u);
	ans.push_back(w);
	while(1){
		if(par[ans.back()] == v) break;
		ans.push_back(par[ans.back()]);
	}
	for(int i : ans)
		cout << i << ' ';
	cout << '\n';
	exit(0);
}

int main(){
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	cin >> n >> m;
	for(int i = 0 ; i < m ; i++){
		int u , v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		mat[u][v] = mat[v][u] = 1;
	}

	for(int v = 1 ; v <= n ; v++)
		mat[v][v] = 1;

	for(int u = 1 ; u <= n ; u++){
		clr();
		mark[u] = 1;
		for(int v : g[u]){
			comp[v].push_back(v);
			mark[v] = 1;
		}

		for(int v = 1 ; v <= n ; v++)
			if(!vis[v])
				dfs(v);

		for(int v : g[u])
			for(int w : comp[get(v)])
				if(!mat[v][w])
					cal(v , u , w);
	}

	cout << "no" << '\n';
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 724 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1656 KB Output is correct
2 Correct 2 ms 1620 KB Output is correct
3 Correct 2 ms 1620 KB Output is correct
4 Correct 7 ms 1620 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4820 KB Output is correct
2 Correct 9 ms 4820 KB Output is correct
3 Correct 139 ms 5424 KB Output is correct
4 Correct 79 ms 4888 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 4512 KB Output is correct
2 Correct 69 ms 4692 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 3092 KB Output is correct
2 Correct 16 ms 3748 KB Output is correct
3 Correct 15 ms 5488 KB Output is correct
4 Correct 145 ms 5584 KB Output is correct