oj.uz

Submission #351259

# Submission time Handle Problem Language Result Execution time Memory
351259 2021-01-19T17:42:35 Z CaroLinda Potemkin cycle (CEOI15_indcyc) C++14
90 / 100
 1000 ms 195232 KB 
#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 ;
 
char C ;
void read(int &num)
{
	num = 0 ;
	for(C = getchar() ; (C > 47 && C < 58 ) ; C = getchar() )
		num = num*10 + C - 48 ;
}

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 , int depth )
{
	height[x] = depth ;
	isOn[x] = true ;
	vis[x] = true ;

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

	isOn[x] = false ;
}
 
int main()
{
 
	read(N) ; read(M) ;
	for(int i = 0 , u , v ; i < M ; i++ )
	{
		read(u) ; read(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 = 0 ; i <= code[N-1][N-1] ; i++ ) vis[i] = false ;

	for(int i = 0 ; i < sz(List) ; i++ )
	{
		if(vis[List[i] ] ) continue ;
		
		dfs2(List[i] ,1 ) ;

		if( lo != -1 ) break ;

	} 
	
	if( lo == -1 )
	{
		printf("no\n") ;
		return 0 ;
	}
 
   vector<int> ans ;

	while(lo != par[hi] )
	{
		ans.push_back(lo%N) ;
		lo = par[lo] ;
	}

 	for(auto e : ans ) printf("%d ", e+1 ) ;
	printf("\n" ) ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Output is correct
2 Correct 28 ms 47340 KB Output is correct
3 Correct 27 ms 47340 KB Output is correct
4 Correct 28 ms 47340 KB Output is correct
5 Correct 28 ms 47468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47340 KB Output is correct
2 Correct 29 ms 47340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 48108 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 48620 KB Output is correct
2 Correct 31 ms 48620 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 50412 KB Output is correct
2 Correct 45 ms 50668 KB Output is correct
3 Correct 51 ms 54592 KB Output is correct
4 Correct 54 ms 54248 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 52972 KB Output is correct
2 Correct 47 ms 53064 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 96096 KB Output is correct
2 Correct 156 ms 69212 KB Output is correct
3 Correct 629 ms 94612 KB Output is correct
4 Correct 169 ms 68824 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 153816 KB Output is correct
2 Correct 437 ms 164308 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 53216 KB Output is correct
2 Correct 135 ms 52580 KB Output is correct
3 Execution timed out 1100 ms 195232 KB Time limit exceeded
4 Halted 0 ms 0 KB -