Submission #702182

#	Time	Username	Problem	Language	Result	Execution time	Memory
702182		ajab_01	Potemkin cycle (CEOI15_indcyc)	C++17	30 / 100	22 ms	5256 KiB

indcyc

#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;
		dis[u] = INF;
	}
}

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);
	comp[v].clear();
}

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){
	clr();
	dq.push_back(v);
	dis[v] = 0;
	while(!dq.empty()){
		int i = dq.front();
		dq.pop_front();
		for(int j : g[i]){
			if(vis[j] || j == u || 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] = {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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10