oj.uz

Submission #115239

# Submission time Handle Problem Language Result Execution time Memory
115239 2019-06-06T08:27:30 Z Adhyyan1252 Potemkin cycle (CEOI15_indcyc) C++11
100 / 100
 351 ms 227016 KB 
#include<bits/stdc++.h>
#define DEBUG false
using namespace std;

vector<vector<int> > g, h;
int n, r;

vector<int> par;

int find(int cur){
	if(par[cur] == cur) return cur;
	return par[cur] = find(par[cur]);
}

void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a == b) return;
	par[b] = a;
}

vector<vector<int> > l;
vector<vector<pair<int, int> > >el;


void bfs(int m, int u, int v){
	vector<int> dist(n, INT_MAX);
	vector<int> dpar(n, -1);
	dist[u] = 0;
	queue<int> q; q.push(u);
	while(!q.empty()){
		int top = q.front(); q.pop();
		for(int ad: g[top]){
			if(ad != u && ad != v && (ad == m || (h[ad][m]))) continue;
			if(dist[ad] == INT_MAX){
				dist[ad] = dist[top]+1;
				q.push(ad);
				dpar[ad] = top;
			}
		}
	}
	assert(dist[v] != INT_MAX);
	vector<int> path = {u, m};
	int cur = v;
	while(cur != u){
		path.push_back(cur);
		cur = dpar[cur];
	}
	for(int i = 0; i < path.size(); i++){
		for(int j = i+1; j < path.size(); j++){
			if(abs(i-j) == 1 || (i == 0 && j == path.size()-1)) continue;
			assert(h[path[i]][path[j]] == false);
		}
	}
	//assert(path.size() >= 4);
	for(int k: path) cout<<k+1<<" ";
	cout<<endl;
	exit(0);
}
vector<bool> ne;
void rec(vector<int> v, vector<pair<int, int> > e){
	if(v.size() < 4) return;	
	if(DEBUG) cout<<"REC: ";
	if(DEBUG) for(int u: v) cout<<u<<" ";
	if(DEBUG) cout<<endl;
	//reset all the dsu of v
	for(int u: v) par[u] = u;
	
	//select main node, and find neighbors
	int m = v[0];
	for(int u: v){
		if(h[u][m]) ne[u] = true;
		else ne[u] = false;
	}
	ne[m] = true;
	
	if(DEBUG) for(int i = 0; i < n; i++) cout<<i<<" : "<<ne[i]<<endl;
	
	for(pair<int, int> ed: e){
		if(ne[ed.first] || ne[ed.second]) continue;
		merge(ed.first, ed.second);
		if(DEBUG) cout<<"MERGE "<<ed.first<<" , "<<ed.second<<endl;
		assert(find(ed.first) == find(ed.second));
	}
	
	for(int u: v) l[u].clear();
	//loop to add all S to G - s - v edges
	for(pair<int, int> ed: e){
		if(ed.first == m || ed.second == m) continue; 
		if(ne[ed.first] && !ne[ed.second]){
			int t = find(ed.second);
			l[t].push_back(ed.first);
			if(DEBUG) cout<<"PUSH "<<t<<" "<<ed.first<<endl;
		}else if(!ne[ed.first] && ne[ed.second]){
			int t = find(ed.first);
			l[t].push_back(ed.second);
			if(DEBUG) cout<<"PUSH "<<t<<" "<<ed.second<<endl;
		}
	}
	if(DEBUG) cout<<"REACHED"<<endl;
	//for each l find
	for(int u: v) el[u].clear();
	for(int u: v){
		sort(l[u].begin(), l[u].end()); l[u].resize(unique(l[u].begin(), l[u].end()) - l[u].begin());
		if(l[u].size() < 2) continue;
		assert(u == find(u));
		if(DEBUG) cout<<"DOING for "<<u<<endl;
		//do a double loop on all pairs to check if they are adjacent
		for(int i = 0; i < l[u].size(); i++){
			for(int j = i+1; j < l[u].size(); j++){
				if(h[l[u][i]][l[u][j]] == false){
					//assert(l[u][i] != l[u][j]);
					//found an answer, output it somehow
					//and then exit
					//find shortest path from i to j without having an edge to m
					bfs(m, l[u][i], l[u][j]);
					assert(false);
				}else{
					el[u].push_back({l[u][i], l[u][j]});
					if(DEBUG) cout<<"PUSH "<<l[u][i]<<" "<<l[u][j]<<endl;
				}
			}
		}
	}
	if(DEBUG) cout<<"REACHED"<<endl;
	vector<int> nel;
	vector<pair<int, int> > edl;
	for(int u: v){
		if(ne[u] && u != m){
			nel.push_back(u);
		}else if(u != m){
			l[find(u)].push_back(u);
		}
	}
	for(pair<int, int>& ed: e){
		if(ne[ed.first] == true && ne[ed.second] == false){
			el[find(ed.second)].push_back(ed);
		}else if(ne[ed.first] == false && ne[ed.second] == true){
			el[find(ed.first)].push_back(ed);
		}else if(ne[ed.first] && ne[ed.second]){
			if(ed.first != m && ed.second != m) {
				edl.push_back(ed);
			}
		}else{
			if(DEBUG) cout<<"L : "<<ed.first<<" "<<ed.second<<" "<<ne[ed.first]<<" "<<ne[ed.second]<<endl;
			assert(find(ed.first) == find(ed.second));
			el[find(ed.first)].push_back(ed);
		}
	}
	if(DEBUG) cout<<"REACHED 1"<<endl;
	for(int u: v){
		for(int k: l[u]) assert(k != m);
		for(auto& k: el[u]) assert(k.first != m && k.second != m);
		if(l[u].size() >= 4) rec(l[u], el[u]);
	}
	for(int k: nel) assert(k != m);
	for(auto& k: edl) assert(k.first != m && k.second != m);
	rec(nel, edl);
	if(DEBUG) cout<<"REACHED 2"<<endl;
}

int main(){
	//assert(false);
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>r;
	g.resize(n);
	h = vector<vector<int> > (n, vector<int>(n));
	par.resize(n);
	l.resize(n); el.resize(n);
	ne.resize(n);
	
	vector<pair<int, int> > elist(r);
	for(int i = 0; i < r; i++){
		int u, v; cin>>u>>v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
		elist[i] = {u, v};
		h[u][v] = 1; h[v][u] = 1;
	}
	
	vector<int> v;
	for(int i = 0; i < n; i++) v.push_back(i);
	rec(v, elist);
	//assert(false);
	cout<<"no"<<endl;
}

Compilation message

indcyc.cpp: In function 'void bfs(int, int, int)':
indcyc.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < path.size(); i++){
                 ~~^~~~~~~~~~~~~
indcyc.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i+1; j < path.size(); j++){
                    ~~^~~~~~~~~~~~~
indcyc.cpp:51:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(abs(i-j) == 1 || (i == 0 && j == path.size()-1)) continue;
                                   ~~^~~~~~~~~~~~~~~~
indcyc.cpp: In function 'void rec(std::vector<int>, std::vector<std::pair<int, int> >)':
indcyc.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < l[u].size(); i++){
                  ~~^~~~~~~~~~~~~
indcyc.cpp:110:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = i+1; j < l[u].size(); j++){
                     ~~^~~~~~~~~~~~~

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

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2176 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 5 ms 1280 KB Output is correct
4 Correct 18 ms 3832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 9772 KB Output is correct
2 Correct 27 ms 11264 KB Output is correct
3 Correct 173 ms 14432 KB Output is correct
4 Correct 54 ms 10360 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7796 KB Output is correct
2 Correct 35 ms 7560 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 51696 KB Output is correct
2 Correct 351 ms 227016 KB Output is correct
3 Correct 172 ms 57176 KB Output is correct
4 Correct 317 ms 68952 KB Output is correct