Submission #24816

#	Time	Username	Problem	Language	Result	Execution time	Memory
24816		noobprogrammer	Potemkin cycle (CEOI15_indcyc)	C++14	20 / 100	1000 ms	5632 KiB

indcyc

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define ii pair<int,int>
#define vii vector<pair<int,int> >
#define vi vector<int>

int mrk[100010] , dist[1010] , n , m , par[1010] , chk = 0  ;
vii adj[1010] , edg ;
vi res ;
queue<ii> q ;
int p[1010][12] ;

int lca(int x,int y){
	if(dist[x] < dist[y]) swap(x,y) ;
	for(int i=11;i>=0;i--) if(dist[p[x][i]] >= dist[y]) x = p[x][i] ;
	if(x == y) return x  ;
	for(int i=11;i>=0;i--) if(p[x][i] != p[y][i]) x = p[x][i] , y = p[y][i] ;
	return p[x][0] ;
}

void bfs(int st){
	for(int i=1;i<=n;i++) dist[i] = 1e9 , par[i] = 0 ;
	dist[st] = 0 ;
	par[st] = st ;
	int cyc = 1e9 ;
	q.push({st ,0} ) ;
	int v , d ;
	memset(mrk , 0 , sizeof mrk) ;
	while(!q.empty()){
		v = q.front().fi ; d  = q.front().se ;
		p[v][0] = par[v] ;
		for(int i=1;i<12;i++) p[v][i] = p[p[v][i-1]][i-1] ;
		q.pop() ;
		for(ii vv : adj[v]){
			if(vv.fi == par[v]) continue ;
			if(dist[vv.fi] <= d+1) continue ;
			dist[vv.fi] = d+1 ; par[vv.fi] = v ; mrk[vv.se] = 1 ;
			q.push({vv.fi , d+1}) ;
		}
	}
	int a , b , opt , lc ;
	for(int i=0;i<m;i++){
		if(mrk[i]) continue ;
		a = edg[i].fi , b = edg[i].se ;
		lc = lca(a,b) ;
		if(lc != st) continue ;
		if(cyc > dist[a]+dist[b] - 2*dist[lc] + 1) {
			cyc = dist[a]+dist[b] - 2*dist[lc] + 1 ;
			opt = i ;
		}
	}
	// printf("--> %d %d\n" ,st ,cyc ) ;
	if(cyc < 4 || cyc == 1e9) return ;
	chk = 1 ;
	a = edg[opt].fi , b = edg[opt].se ;
	while(1){
		res.push_back(a) ;
		if(a == st) break ;
		a = par[a] ;
	}
	reverse(res.begin() , res.end()) ;
	while(b!=st){
		res.push_back(b) ;
		b = par[b] ;
	}
	for(int i=0;i<res.size();i++) printf("%d ",res[i]) ;
}

int main(){
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
	scanf("%d%d",&n,&m) ;
	int a ,b ;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b) ;
		adj[a].push_back({b,i}) ;
		adj[b].push_back({a,i}) ;
		edg.push_back({a,b}) ;
	}
	for(int i=1;i<=n;i++){
		bfs(i) ;
		if(chk) return 0 ;
	}
	printf("no") ;
	return 0;
}

Compilation message (stderr)

indcyc.cpp: In function 'void bfs(int)':
indcyc.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<res.size();i++) printf("%d ",res[i]) ;
               ^
indcyc.cpp: In function 'int main()':
indcyc.cpp:75:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m) ;
                      ^
indcyc.cpp:78:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b) ;
                       ^
indcyc.cpp: In function 'void bfs(int)':
indcyc.cpp:58:13: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  a = edg[opt].fi , b = edg[opt].se ;
             ^

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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