Japanese Olympiad in Informatics Spring Camp 2018

Alice.cpp

// Ivan Carvalho
// Airline Route Map - JOI SC 2018
#include "Alicelib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1020;
 
static vector<int> grafo[MAXN];
 
void Alice( int N, int M, int A[], int B[] ){
	
  // Hard coded small cases
	if(N == 1){
		InitG(1,0);
		return;
	}
 
	if(N == 2){
		if(M == 0){
			InitG(2,0);
		}
		else{
			InitG(2,1);
			MakeG(0,0,1);
		}
		return;
	}	
 
	// Original graph
	for(int i = 0;i<M;i++){
		int x = A[i];
		int y = B[i];
		x++;y++; // 1-indexed, this is important!
		grafo[x].push_back(y);
		grafo[y].push_back(x);
	}
 
	int qtd_n = N + 12;
	int qtd_m = 0;
 
	// Bits
	for(int i = 0;i<10;i++){
		int pot = (1 << i);
		int idx = N + i + 1;
		for(int j = 1;j<=N;j++){
			if(pot & j){
				grafo[j].push_back(idx);
				grafo[idx].push_back(j);
			}
		}
	}
 
	// Bit-chain
	for(int i = 0;i+1<10;i++){
		int idx1 = N + i + 1;
		int idx2 = N + i + 2;
		grafo[idx1].push_back(idx2);
		grafo[idx2].push_back(idx1);
	}
 
	// Vertex of degree one
	grafo[N+11].push_back(N+12);
	grafo[N+12].push_back(N+11);
 
	// Edge that connects to all vertices except the bits
	for(int i = 1;i<=N;i++){
		grafo[i].push_back(N+12);
		grafo[N+12].push_back(i);
	}
 
  // Counting the number of edges
	for(int i = 1;i<=N+12;i++) qtd_m += grafo[i].size();
	qtd_m /=2;
 
	InitG(qtd_n,qtd_m);
	int ptr = 0;
	for(int i = 1;i<=N+12;i++){
		for(int j : grafo[i]){
			if(i >= j) continue;
			MakeG(ptr,i-1,j-1);
			ptr++;
		}
	}
 
}

Bob.cpp

// Ivan Carvalho
// Airline Route Map - JOI SC 2018
#include "Boblib.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1020;
 
static vector<int> grafo[MAXN];
static int ehValido[MAXN],somatorio[MAXN];
 
void Bob( int V, int U, int C[], int D[] ){
 
	memset(ehValido,0,sizeof(ehValido));
	memset(somatorio,0,sizeof(somatorio));
 
	// Hardcoded cases
	if(V == 1){
		InitMap(1,0);
		return;
	}
 
	if(V == 2){
		if(U == 0){
			InitMap(2,0);
		}
		else{
			InitMap(2,1);
			MakeMap(0,1);
		}
		return;
	}
	
	int N = V - 12,M = 0,especial = 0,bit_davez = 0;
 
  // Building the graph
	for(int i = 0;i<U;i++){
		int x = C[i];
		int y = D[i];
		x++;y++;
		grafo[x].push_back(y);
		grafo[y].push_back(x);
	}
 
	vector<int> candidatos;
 
  // Finding the leaves
	for(int i = 1;i<=N+12;i++){
		if(grafo[i].size() == 1) candidatos.push_back(i);
	}
 
	if(candidatos.size() == 1){
		int folha = candidatos[0];
		especial = grafo[folha][0];
		for(int i : grafo[especial]){
			ehValido[i] = 1;
		}
		int menor_grau = 1024;
		for(int i = 1;i<=N+12;i++){
			if(ehValido[i]) continue;
			if(grafo[i].size() <= menor_grau){
				menor_grau = grafo[i].size();
				bit_davez = i;
			}
		}
	}
	else if(candidatos.size() == 2){
		int primeiro_cand = candidatos[0];
		int outro_cara = grafo[primeiro_cand][0];
		if(grafo[outro_cara].size() == N + 1){
			especial = outro_cara;
			bit_davez = candidatos[1];
		}
		else{
			bit_davez = primeiro_cand;
			especial = grafo[candidatos[1]][0];
		}
		for(int i : grafo[especial]){
			ehValido[i] = 1;
		}
	}
 
	ehValido[candidatos[0]] = 0;
	if(candidatos.size() == 2) ehValido[candidatos[1]] = 0;
 
  // Processing the bits for each vertex
 	for(int vez = 9;vez>=0;vez--){
 		
 		int nxt = 0,pot = (1 << vez);
 
 		for(int i : grafo[bit_davez]){
 			if(grafo[i].size() <= 1){
 				continue;
 			}
 			if(!ehValido[i]){
 				nxt = i;
 			}
 			else{
 				somatorio[i] += pot;
 			}
 		}
 
 		grafo[bit_davez].clear();
 
 		bit_davez = nxt;
 
 	}
 
  // Counting the edges
 	for(int i = 1;i<=N+12;i++){
 		for(int j : grafo[i]){
 			if(!ehValido[i] || !ehValido[j]) continue;
 			if(i <= j){
 				M++;
 			}
 		}
 	}
 
 	InitMap(N,M);
 
  // Sending the original graph
 	for(int i = 1;i<=N+12;i++){
 		for(int j : grafo[i]){
 			if(!ehValido[i] || !ehValido[j]) continue;
 			if(i <= j){
 				MakeMap(somatorio[i] - 1,somatorio[j] - 1);
 			}
 		}
 	}
 
}