Submission #702248

#	Time	Username	Problem	Language	Result	Execution time	Memory
702248		amirhoseinfar1385	Potemkin cycle (CEOI15_indcyc)	C++17	20 / 100	1060 ms	5144 KiB

indcyc

   #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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10