oj.uz

Submission #589438

# Submission time Handle Problem Language Result Execution time Memory
589438 2022-07-04T17:03:54 Z Blagojce Potemkin cycle (CEOI15_indcyc) C++11
30 / 100
 1000 ms 877796 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int mxn = 1003;
mt19937 _rand(time(NULL));
clock_t z;

int n, m;
vector<int> g[mxn];	
bool adj[mxn][mxn];

int vis[mxn];
int uniq = 0;
int uniq2 = 0;
int aux[mxn];
int aux2[mxn];

int parent[mxn];


void expand(int r, int x, int y){
	uniq ++;
	queue<int> Q;
	Q.push(x);
	vis[x] = uniq;
	vis[r] = uniq;
	
	parent[x] = x;
	
	while(!Q.empty()){
		int c = Q.front();
		Q.pop();
		
		for(auto e : g[c]){
			if(vis[e] == uniq) continue;
			vis[e] = uniq;
			
			parent[e] = c;
			Q.push(e);
			
		}
	}
	
	vector<int> sol;
	sol.pb(r);
	sol.pb(y);
	while(sol.back() != x){
		sol.pb(parent[sol.back()]);
	}
	for(auto u : sol) cout<<u+1<<' ';
	cout<<endl;
	exit(0);
}


vector<int> check(vector<int> G, int r){
	vector<int> S;
	uniq2 ++;
	for(auto u : G) aux2[u] = uniq2;
	
	
	for(auto u : g[r]){
		if(aux[u] != uniq) continue;
		
		for(auto e : g[u]){
			if(aux[e] != uniq) continue;
			
			if(aux2[e] == uniq2){
				S.pb(u);
				break;
			}
			
		}
	}
	fr(i, 0, (int)S.size()){
		fr(j, i+1, (int)S.size()){
			if(!adj[S[i]][S[j]]){
				expand(r, S[i], S[j]);
			}
		}
	}
	
	for(auto u : S) G.pb(u);
	
	return G;
}


vector<vector<int> > generate_next(vector<vector<int> > G, int r){
	fr(i, 0, (int)G.size()){
		G[i] = check(G[i], r); 
	}
	
	vector<int> S;
	for(auto u : g[r]){	
		S.pb(u);
	}
	G.pb(S);
	
	return G;
}



vector<int> gp;
void dfs(int u){
	gp.pb(u);
	
	vis[u] = uniq;
	for(auto e : g[u]){
		if(aux[e] != uniq || vis[e] == uniq) continue;
		
		dfs(e);
	}
}



vector<vector<int> > split(vector<int> v, int r){
	++uniq;
	for(auto u : v) aux[u] = uniq;
	
	vis[r] = uniq;
	for(auto u : g[r]) vis[u] = uniq;
	
	vector<vector<int> > G;
	for(auto u : v){
		if(vis[u] == uniq) continue;
		gp.clear();
		dfs(u);
		G.pb(gp);
	}
	return G;
}

void solve(vector<int> v){
	if((int)v.size() < 4) return;
	
	int r = v[0];
	vector<vector<int> > G = split(v, r);
	
	
	G = generate_next(G, r);
	
	for(auto Gp : G){
		solve(Gp);
	}
}


int main(){
	cin >> n >> m;
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].pb(v);
		g[v].pb(u);
		adj[u][v] = true;
		adj[v][u] = true;
	}
	
	vector<int> v;
	fr(i, 0, n) v.pb(i);
	solve(v);
	
	cout<<"no"<<endl;
}

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

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 340 KB Output is correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 171528 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 1140 ms 877796 KB Time limit exceeded
2 Halted 0 ms 0 KB -