Submission #46858

#	Time	Username	Problem	Language	Result	Execution time	Memory
46858		HachikujiMayoi	Potemkin cycle (CEOI15_indcyc)	C++14	30 / 100	27 ms	5668 KiB

indcyc

#include <bits/stdc++.h>

using namespace std;

const int N = 1007;

int n, m;
int blocked[N], par[N], vis[N];
vector <int> g[N], comp[N];
int G[N][N];

int Get(int a){
	if(par[a] == a) return a;
	return par[a] = Get(par[a]);
}

void Union(int a, int b){
	a = Get(a);
	b = Get(b);
	if(a == b) return;
	if(comp[b].size() > comp[a].size()) swap(a, b);
	par[b] = a;
	for(auto i : comp[b]) comp[a].push_back(i);
}

void dfs(int at){
	if(blocked[at]) return;
	vis[at] = 1;
	for(auto i : g[at]){
		if(!vis[i]){
			Union(at, i);
			dfs(i);
		}
	}
}

void solve(int a, int b, int c){
	blocked[a] = 0;
	blocked[c] = 0;
	vector <int> dis(n + 1, N), dad(n + 1, 0);
	queue <int> q;
	dis[a] = 0;
	q.push(a);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(auto i : g[u]){
			if(blocked[i]) continue;
			if(dis[i] > dis[u] + 1){
				dis[i] = dis[u] + 1;
				dad[i] = u;
				q.push(i);
			}
		}
	}
	printf("%d %d %d", a, b, c);
	int cur = dad[c];
	while(cur != a){
		printf(" %d", cur);		
		cur = dad[cur];
	}
	printf("\n");
}

int main(){
	int x, y;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i){
		scanf("%d %d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
		G[x][y] = 1;
		G[y][x] = 1;
	}
	for(int i = 1; i <= n; ++i) G[i][i] = 1;
	for(int i = 1; i <= n; ++i){
		memset(blocked, 0, sizeof(blocked));
		memset(vis, 0, sizeof(vis));
		blocked[i] = 1;
		for(auto j : g[i]){
			blocked[j] = 1;
		}
		for(int j = 1; j <= n; ++j){
			if(blocked[j]) comp[j] = {j};
			par[j] = j;
		}
		for(int j = 1; j <= n; ++j){
			if(!vis[j]) dfs(j);
		}
		for(int j : g[i]){
			int k = Get(j);
			for(auto o : comp[k]){
				if(!G[j][o]){
					solve(j, i, o);
					return 0;
				}
			}
		}
	}
	printf("no\n");
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
indcyc.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

• 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