Submission #142655

#	Time	Username	Problem	Language	Result	Execution time	Memory
142655		nots0fast	Potemkin cycle (CEOI15_indcyc)	C++17	50 / 100	1056 ms	6352 KiB

indcyc

#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(12)<<fixed
#define ss second
#define fori(v) for(int i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define ll long long int
#define double long double
#define MAX (int)(pow(10,3)+ 10)
#define pb(a) push_back(a)
// #define cout out
// #define cin in
ll inf = pow(10,18);
ll modulo = 1000007;
double eps = 1e-10;
ifstream in;
ofstream out;


void deal(){
	ll n, r;
	cin>>n>>r;
	vector<vector<ll> > g(n);
	fori(r){
		ll a, b;
		cin>>a>>b; --a, --b;
		g[a].pb(b), g[b].pb(a);
	}
	fori(n){
		vector<ll> bfs(1,i);
		vector<vector<ll> > taken(n);
		vector<vector<ll> > untaken(n);
		vector<ll> dist(n, inf);
		vector<ll> par(n , -1);
		vector<ll> root(n,-1);
		vector<ll> bad(n,0);
		dist[i] = 0;
		forj(bfs.size()){
			ll hd = bfs[j];
			for(auto hr : g[hd]){
				if(dist[hd] + 1 < dist[hr]){
					dist[hr] = (dist[hd] + 1);
					par[hr] = hd;
					taken[hd].pb(hr);
					bfs.pb(hr);
				}
				else if(hr != par[hd] ){
					untaken[hr].pb(hd);
					untaken[hd].pb(hr);
				}
			}
		}
		for(auto el : g[i]){
			stack<ll> dfs;
			dfs.push(el);
			while(dfs.size()){
				ll hd = dfs.top();
				dfs.pop();
				root[hd] = el;
				for(auto hr : taken[hd])
					dfs.push(hr);
			}
		}
		for(auto el : g[i]){
			for(auto el2 : untaken[el])
				if(dist[el2] == 1)
					bad[el2] = 1;
			stack<ll> dfs;
			dfs.push(el);
			ll lz = -1, lz1 = -1;
			while(dfs.size()){
				ll hd = dfs.top();
				for(auto hr : untaken[hd]){
					if(!bad[root[hr]] && root[hr] != el){
						lz = hd;
						lz1 = hr;
						break;
					}
				}
				if(lz!=-1)
					break;
				dfs.pop();
				for(auto hr : taken[hd])
					dfs.push(hr);
			}
			for(auto el2 : untaken[el])
				bad[el2] = 0;
			if(lz!=-1){
				ll hd = lz;
				ll mn = lz1;
				for(auto el : untaken[hd])
					if(root[el] == root[mn] && dist[el] < dist[mn])
						mn = el;
				vector<ll> seq;
				while(mn!=i){
					seq.pb(mn);
					mn = par[mn];
				}
				reverse(seq.begin(), seq.end());
				seq.pb(hd);
				do{
					hd = par[hd];
					seq.pb(hd);
				}while(hd!=i);
				assert(seq.size()>=4);
				for(auto el : seq)
					cout<<el+1<<' ';
				return;
			}
		}
	}
	cout<<"no";
}
 

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}



/* 
6 8 
1 2
2 3
3 4
4 1
2 5
3 5
1 6
4 6
*/

Compilation message (stderr)

indcyc.cpp: In function 'void deal()':
indcyc.cpp:8:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forj(v) for(int j=0; j<v; j++)
                              ~^~~~~~~~~
 #define fork(v) for(int k=0; k<v; k++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define forl(v) for(int l=0; l<v; l++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define fort(v) for(int t=0; t<v; t++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define forz(v) for(int z=0; z<v; z++)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define ll long long int
 ~~~~~~~~~~~~~~~~~~~~~~~~~      
 #define double long double
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~    
 #define MAX (int)(pow(10,3)+ 10)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 #define pb(a) push_back(a)
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~    
 // #define cout out
 ~~~~~~~~~~~~~~~~~~~~           
 // #define cin in
 ~~~~~~~~~~~~~~~~~~             
 ll inf = pow(10,18);
 ~~~~~~~~~~~~~~~~~~~~~          
 ll modulo = 1000007;
 ~~~~~~~~~~~~~~~~~~~~~          
 double eps = 1e-10;
 ~~~~~~~~~~~~~~~~~~~~           
 ifstream in;
 ~~~~~~~~~~~~~                  
 ofstream out;
 ~~~~~~~~~~~~~~                 
 
 ~                              
 
 ~                              
 void deal(){
 ~~~~~~~~~~~~~                  
  ll n, r;
  ~~~~~~~~~                     
  cin>>n>>r;
  ~~~~~~~~~~~                   
  vector<vector<ll> > g(n);
  ~~~~~~~~~~~~~~~~~~~~~~~~~~    
  fori(r){
  ~~~~~~~~~                     
   ll a, b;
   ~~~~~~~~~                    
   cin>>a>>b; --a, --b;
   ~~~~~~~~~~~~~~~~~~~~~        
   g[a].pb(b), g[b].pb(a);
   ~~~~~~~~~~~~~~~~~~~~~~~~     
  }
  ~~                            
  fori(n){
  ~~~~~~~~~                     
   vector<ll> bfs(1,i);
   ~~~~~~~~~~~~~~~~~~~~~        
   vector<vector<ll> > taken(n);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   vector<vector<ll> > untaken(n);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   vector<ll> dist(n, inf);
   ~~~~~~~~~~~~~~~~~~~~~~~~~    
   vector<ll> par(n , -1);
   ~~~~~~~~~~~~~~~~~~~~~~~~     
   vector<ll> root(n,-1);
   ~~~~~~~~~~~~~~~~~~~~~~~      
   vector<ll> bad(n,0);
   ~~~~~~~~~~~~~~~~~~~~~        
   dist[i] = 0;
   ~~~~~~~~~~~~~                
   forj(bfs.size()){
   ~~~~~~~~~~~~~~~              
indcyc.cpp:44:3: note: in expansion of macro 'forj'
   forj(bfs.size()){
   ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10