Central-European Olympiad in Informatics 2016

icc.cpp

// Ivan Carvalho
// ICC - CEOI 2016
// O(N*log(N))
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 110;
 
int pai[MAXN],N;
vector<int> filhos[MAXN];
int cjt_a[MAXN],cjt_b[MAXN],szA,szB;
 
int find(int x){
	if(x == pai[x]) return x;
	return pai[x] = find(pai[x]);
}
 
void join(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	if(x < y) swap(x,y);
	pai[y] = x;
	for(int z : filhos[y]) filhos[x].push_back(z);
}
 
int doQuery(vector<int> A,vector<int> B){
	if(A.empty() || B.empty()) return 0;
	szA = 0;
	szB = 0;
	memset(cjt_a,0,sizeof(cjt_a));
	memset(cjt_b,0,sizeof(cjt_b));
	for(int i : A){
		cjt_a[szA] = i;
		szA++;
	}
	for(int i : B){
		cjt_b[szB] = i;
		szB++;
	}
	return query(szA,szB,cjt_a,cjt_b);
}
 
int solve(vector<int> unknown_nodes, vector<int> fixed_nodes ){
 
	if(unknown_nodes.size() == 1) return unknown_nodes[0];
 
	vector<int> firstHalf,secondHalf;
	int m = unknown_nodes.size()/2;
	for(int i = 0;i<unknown_nodes.size();i++){
		if(i < m) firstHalf.push_back(unknown_nodes[i]);
		else secondHalf.push_back(unknown_nodes[i]);
	}
 
	if(doQuery(firstHalf,fixed_nodes)) return solve(firstHalf,fixed_nodes);
	else return solve(secondHalf,fixed_nodes);
 
}
 
int test_partition(int bit,vector<int>& A,vector<int>& B,vector<int> possible,int flag){
	for(int i = 0;i<possible.size();i++){
		int j = possible[i];
		if(i & (1 << bit)){
			for(int k : filhos[j]) A.push_back(k);
		}
		else{
			for(int k : filhos[j]) B.push_back(k);
		}
	}
	if(flag) return 1;
	else return doQuery(A,B);
}
 
void discover_edge(){
 
	vector<int> possiveis,quaisbits,A,B;
 
	for(int i = 1;i<=N;i++){
		if(find(i) == i) possiveis.push_back(i);
	}
 
	for(int i = 0;(1 << i) <= possiveis.size();i++) quaisbits.push_back(i);
	random_shuffle(quaisbits.begin(),quaisbits.end());
 
	for(int j = 0;j<quaisbits.size();j++){
		A.clear();
		B.clear();
		int i = quaisbits[j],flag = (j == quaisbits.size() - 1);
		if(!test_partition(i,A,B,possiveis,flag)) continue;
		int x = solve(A,B);
		int y = solve(B,A);
		join(x,y);
		setRoad(x,y);
		break;
	}
 
}
 
void run(int n){
	N = n;
 
	for(int i = 1;i<=N;i++){
		pai[i] = i;
		filhos[i].push_back(i);
	}
 
	for(int i = 1;i<N;i++){
		discover_edge();
	}
 
}