Submission #351249

#	Time	Username	Problem	Language	Result	Execution time	Memory
351249		CaroLinda	Potemkin cycle (CEOI15_indcyc)	C++14	90 / 100	1109 ms	195136 KiB

indcyc

#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
 
const int MAX = 1e6+10 ;
const int MAXN = 1010 ;
 
using namespace std ;
 
int N , M ;
int minDiff = MAX , lo = -1 , hi = -1 ;
vector<int> trash[MAXN] , adj[MAX] , revAdj[MAX]  ;
int height[MAX] , par[MAX] , comp[MAX] ;
int code[MAXN][MAXN] ;
bool mat[MAXN][MAXN] ;
bool vis[MAX],isOn[MAX] ;
 
vector<int> List ;
void dfs1(int x)
{	
	vis[x] = true ;
	for(auto e : adj[x] )
		if(!vis[e] ) dfs1(e) ;
	List.push_back(x) ;
}
 
void dfs2(int x )
{
	for(auto e : revAdj[x] )
		if(!comp[e])
		{
			comp[e] = comp[x] ;
			dfs2(e) ;
		}
}
 
void dfs3(int x , int depth )
{
	height[x] = depth ;
	isOn[x] = true ;

	for(auto e : adj[x] ) 
	{
		if( comp[e] != comp[x] || e == par[x] ) continue ;
		if( height[e] )
		{
			if( isOn[e] && height[x] - height[e] < minDiff )
			{
				minDiff = height[x] - height[e] ;
				lo = x ;
				hi = e ;
			}
			continue ;
		}
 
		par[e] = x ;
		dfs3(e,depth+1) ;
 
	}

	isOn[x] = false ;
}
 
int main()
{
 
	scanf("%d %d", &N, &M ) ;
	for(int i = 0 , u , v ; i < M ; i++ )
	{
		scanf("%d %d", &u, &v ) ;
		--u ; --v ;
	
		mat[u][v] = mat[v][u] = true ;
 
		trash[u].push_back(v) ;
		trash[v].push_back(u) ;
	}
 
	for(int i = 0 , c = 0 ; i < N ; i++  )
		for(int j = 0 ; j < N ; j++ , c++ ) code[i][j] = c ;
 
	for(int i = 0  ; i < N ; i++ )
		for(int j = 0 ; j < N ; j++ )
		{
			if( i == j || !mat[i][j] ) continue ;
 
			for(auto k : trash[j] )
			{
				if(mat[i][k] || i == k) continue ; 		
 
				adj[ code[i][j] ].push_back( code[j][k] ) ;
				revAdj[ code[j][k] ].push_back(code[i][j] ) ;
			}
 
		}
 
	for(int i = 0 ; i < N ; i++ )
		for(int j= 0 ; j < N ; j++ )
		{
			if( i == j || vis[ code[i][j] ] ) continue ;
			dfs1(code[i][j] ) ;
		}
 
	for(int i = sz(List)-1 ,c = 0 ; i >= 0 ; i-- )
	{
		if(comp[ List[i] ] ) continue ;
		comp[ List[i] ] = ++c ;
		dfs2(List[i] ) ;
	}
 
	for(int i = 0 ; i <= code[N-1][N-1] ; i++ ) vis[i] = false ;
 
	for(int e : List )
	{
		if(vis[ comp[e] ] ) continue ;
		vis[ comp[e] ] = true ;
		dfs3(e, 1) ;
		if(lo != -1 ) break ;		
	}
	
	if( lo == -1 )
	{
		printf("no\n") ;
		return 0 ;
	}
 
	set<int> s ;
	while(lo != par[hi] )
	{
		s.insert( lo%N ) ;
		s.insert(lo/N ) ;
		lo = par[lo] ;
	}
 
	vector<int> ans ;
 
	int x = *s.begin() ;
	while(sz(s) )
	{
		s.erase(s.find(x) ) ;
		ans.push_back(x) ;
		for(auto e : trash[x] )
			if( s.find(e) != s.end() )
			{
				x = e; 
				break ;
			}
	}
 
	for(auto e : ans ) printf("%d ", e+1 ) ;
	printf("\n" ) ;
}

Compilation message (stderr)

indcyc.cpp: In function 'int main()':
indcyc.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("%d %d", &N, &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
indcyc.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%d %d", &u, &v ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 0 / 10