oj.uz

Submission #351249

# Submission time Handle Problem Language Result Execution time Memory
351249 2021-01-19T17:30:23 Z CaroLinda Potemkin cycle (CEOI15_indcyc) C++14
90 / 100
 1000 ms 195136 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 ;
 
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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47488 KB Output is correct
2 Correct 30 ms 47340 KB Output is correct
3 Correct 30 ms 47340 KB Output is correct
4 Correct 30 ms 47340 KB Output is correct
5 Correct 30 ms 47488 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47468 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 31 ms 48108 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 50796 KB Output is correct
2 Correct 41 ms 50924 KB Output is correct
3 Correct 55 ms 54508 KB Output is correct
4 Correct 57 ms 54652 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 53228 KB Output is correct
2 Correct 48 ms 53348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 618 ms 99884 KB Output is correct
2 Correct 207 ms 73180 KB Output is correct
3 Correct 636 ms 98644 KB Output is correct
4 Correct 194 ms 72796 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 157532 KB Output is correct
2 Correct 452 ms 168276 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 54752 KB Output is correct
2 Correct 157 ms 54116 KB Output is correct
3 Execution timed out 1109 ms 195136 KB Time limit exceeded
4 Halted 0 ms 0 KB -