oj.uz

Submission #142654

# Submission time Handle Problem Language Result Execution time Memory
142654 2019-08-10T09:51:47 Z nots0fast Potemkin cycle (CEOI15_indcyc) C++17
50 / 100
 1000 ms 6808 KB 
#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);
	ll t;
	t = 1;
	while(t--)
	deal(), cout<<'\n';
}



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

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 376 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 668 KB Output is correct
2 Correct 5 ms 656 KB Output is correct
3 Correct 11 ms 816 KB Output is correct
4 Correct 183 ms 848 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 708 KB Expected integer, but "no" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3952 KB Output is correct
2 Correct 45 ms 2172 KB Output is correct
3 Execution timed out 1071 ms 3984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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