oj.uz

Submission #351260

# Submission time Handle Problem Language Result Execution time Memory
351260 2021-01-19T17:46:15 Z CaroLinda Potemkin cycle (CEOI15_indcyc) C++14
100 / 100
 344 ms 146908 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 ;

	for(auto e : adj[x] ) 
	{
		if( isOn[e] && height[x] - height[e] < minDiff )
		{
			minDiff = height[x] - height[e] ;
			lo = x ;
			hi = e ;
		}
		if(height[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 ) adj[ code[i][j] ].push_back( code[j][k] ) ; 
		}
 
	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 < sz(List) ; i++ )
	{
		if(height[List[i]]) continue ;
		
		dfs2(List[i] ,1 ) ;

		if( lo != -1 ) break ;

	} 
	
	if( lo == -1 )
	{
		printf("no\n") ;
		return 0 ;
	}

	while(lo != par[hi] )
	{
		printf("%d ", (lo%N)+1 ) ;
		lo = par[lo] ;

	}
}

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 28 ms 47340 KB Output is correct
4 Correct 28 ms 47340 KB Output is correct
5 Correct 28 ms 47340 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 29 ms 47340 KB Output is correct
2 Correct 30 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 48364 KB Output is correct
2 Correct 31 ms 48236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 50148 KB Output is correct
2 Correct 33 ms 50276 KB Output is correct
3 Correct 40 ms 52324 KB Output is correct
4 Correct 42 ms 51940 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 51428 KB Output is correct
2 Correct 39 ms 51428 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 79332 KB Output is correct
2 Correct 86 ms 65880 KB Output is correct
3 Correct 192 ms 77528 KB Output is correct
4 Correct 93 ms 65368 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 105944 KB Output is correct
2 Correct 196 ms 110812 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 52704 KB Output is correct
2 Correct 136 ms 52616 KB Output is correct
3 Correct 297 ms 146908 KB Output is correct
4 Correct 344 ms 145772 KB Output is correct