oj.uz

Submission #115861

# Submission time Handle Problem Language Result Execution time Memory
115861 2019-06-09T11:16:10 Z rajarshi_basu Potemkin cycle (CEOI15_indcyc) C++14
40 / 100
 1000 ms 2296 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <stack>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>

using namespace std;

const int INF = 1e9+10;
const int MAXN = 1000+10;

int n,m;
bool mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
bool validEdge[MAXN][MAXN];

stack<ii> cyc;
set<int> allnode;
bool done = 0;

inline bool isok(int a,int b,int c){
	return (!(mat[a][b] and mat[b][c] and mat[a][c])) and mat[b][c];
}

void dfs1(ii node){
	if(done)return;
	cyc.push(node);
	//cout << node.ff << " " << node.ss << endl;
	if(vis[node.ff][node.ss]){
		// we got our cycle

		allnode.insert(node.ff);
		allnode.insert(node.ss);
		validEdge[node.ff][node.ss] = validEdge[node.ss][node.ff] = 1;
		cyc.pop();
		while(cyc.size()>0){
			ii x = cyc.top();cyc.pop();
			validEdge[x.ff][x.ss] = validEdge[x.ss][x.ff] = 1;
			allnode.insert(x.ff);
			allnode.insert(x.ss);	
			if(x == node)break;
		}	
		done = 1;
		return;
	}

	FOR(nxt,n){
		if(nxt == node.ff)continue;
		if(isok(node.ff,node.ss,nxt)){
			// this is a valid edge;
			vis[node.ff][node.ss] = 1;
			dfs1({node.ss,nxt});
			vis[node.ff][node.ss] = 0;
	
			if(done)return;
		}

	}

	if(cyc.size()>0)cyc.pop();
}

bool impNode[MAXN];
bool vis2[MAXN];
stack<int> st;
vector<int> cc;
void dfs2(int node,int p = -1){
	if(done)return;
	st.push(node);
	//cout << node << endl;
	cc.pb(node);
  	vis2[node] = 1;
	FOR(i,n){
		if(node == i)continue;
		if(p == i)continue;
		if(done)return;
		/*
		if(mat[node][i] and vis2[i] and impNode[i] and !validEdge[node][i]){
			st.pop();
			while(!st.empty()){
				int x = st.top();st.pop();
				cc.pb(x);
				if(x == i)break;
			}
			done = 1;
			return;
		}*/

		if(validEdge[node][i]){
			if(vis2[i]){
				//st.pop();

				/*while(!st.empty()){
					int x = st.top();st.pop();
					cc.pb(x);
					if(x == i)break;
				}
				done = 1;*/
			}else{
				dfs2(i,node);	
			}
			
		}
		if(done)return;
	}
	if(st.size()>0)st.pop();
}

int main(){
	cin >> n >> m;
	FOR(i,m){
		int a,b;
		cin >> a >> b;
		a--;b--;
		mat[a][b] = mat[b][a] = 1;
	}
	// input done
	FOR(i,n){
		dfs1({i,i});
	}
	if(!done){
		cout << "no" << endl;
		return 0;
	}
	int x;
	for(auto e:allnode){
		impNode[e] = 1;
		x = e;
	}
	for(auto e:allnode){
		//cout << e << endl;
	}
	done = 0;
	dfs2(x);
	
	if(cc.empty()){
		cout << "no"+to_string(allnode.size()) << endl;
	}else{
		for(auto e:cc){
			cout << e+1 << " ";
		}
		cout << endl;
	}
	return 0;
}

Compilation message

indcyc.cpp: In function 'int main()':
indcyc.cpp:155:11: warning: unused variable 'e' [-Wunused-variable]
  for(auto e:allnode){
           ^
indcyc.cpp:159:6: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dfs2(x);
  ~~~~^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Wrong adjacency

Subtask #5
10.0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 768 KB Output is correct
2 Execution timed out 1062 ms 888 KB Time limit exceeded

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 1852 KB Output is correct
2 Execution timed out 1052 ms 2012 KB Time limit exceeded

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 888 KB Output is correct
2 Correct 207 ms 1248 KB Output is correct
3 Correct 109 ms 2176 KB Output is correct
4 Execution timed out 1079 ms 2296 KB Time limit exceeded