oj.uz

Submission #702248

# Submission time Handle Problem Language Result Execution time Memory
702248 2023-02-23T11:23:14 Z amirhoseinfar1385 Potemkin cycle (CEOI15_indcyc) C++17
20 / 100
 1000 ms 5144 KB 
   #include<bits/stdc++.h>
   using namespace std;
   const int maxn=1000+5;
   int par[maxn],vis[maxn],len[maxn];
   vector<int>adj[maxn];
   int n,m;
   vector<int>res,resl,resr;
   vector<int>fb;
   int adjmat[maxn][maxn];
   int had;
   void solve(int lena=0){
   	if((int)fb.size()==0){
   		return ;
   	}
   	for(auto x:fb){
   		len[x]=lena;
   		vis[x]=1;
   	}
   	vector<int>fake;
   	for(auto x:fb){
   		for(auto y:adj[x]){
   			if(vis[y]==1){
   				continue;
   			}
   			else if(!(lena==0&&had==y)){
   				if(lena==0&&adjmat[y][had]==1){
   					continue;
   				}
   				vis[y]=1;
   				len[y]=lena+1;
   				par[y]=x;
   				fake.push_back(y);
   			}
   		}
   	}
   	fb.swap(fake);
   	solve(lena+1);
   }
    
   int main(){
   	ios::sync_with_stdio(0);
   	cin.tie(0);
   	cout.tie(0);
   	cin>>n>>m;
   	for(int i=0;i<m;i++){
   		int u,v;
   		cin>>u>>v;
   		adj[u].push_back(v);
   		adj[v].push_back(u);
   		adjmat[u][v]=1;
   	}
   	for(int i=1;i<=n;i++){
   		for(auto x:adj[i]){
   			if(x>i){
   				for(int i=0;i<maxn;i++){
   					par[i]=vis[i]=len[i]=0;
   				}
   				fb.clear();
   				fb.push_back(x);
   				had=i;
   				solve();
   			//	cout<<x<<" "<<i<<" "<<len[i]<<"\n";
   				if(len[i]>2){
   					int now=i;
   					while(now>0){
   						cout<<now<<" ";
   						now=par[now];
   					}
   					return 0;
   				}
   			}
   		}
   	}
   	if(res.size()==0){
   		cout<<"no\n";
   	}
   	else{
   		for(auto x:res){
   			cout<<x<<" ";
   		}
   		cout<<"\n";
   	}
   }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 616 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1524 KB Wrong answer on graph without induced cycle
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1236 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 5144 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3796 KB Wrong adjacency
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 3736 KB Time limit exceeded
2 Halted 0 ms 0 KB -