Japanese Olympiad in Informatics Open Contest 2017

Ioi.cpp

// Ivan Carvalho
// Amusement Park - JOI Open 2017
#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 10011;
const int MAXL = 60;
 
static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],qual_digito[MAXN],relevante[MAXN];
 
static void bfs(){
 
	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);
 
	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}
 
	memset(contador,0,sizeof(contador));
 
}
 
static void build_first(){
 
	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}
 
	for(int i : primeiro) tree[i] = primeiro;
 
}
 
static void extend_tree(int v){
 
	vector<int> copia = tree[pai[v]];
 
	for(int u : copia){
		for(int w : copia){
			if(adjMat[u][w] && u < w){
				contador[u]++;
				contador[w]++;
			}
		}
	}
 
	int achei = -1;
 
	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}
 
	for(int u : copia){
		contador[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}
 
	tree[v].push_back(v);
	idx[v] = idx[achei];
 
}
 
static void dfs(int v){
 
	contador[v] = 1;
	digito[idx[v]] = qual_digito[v];
 
	for(int u : grafo[v]){
		if(!adjMat[u][v] || contador[u] || !relevante[u]) continue;
		qual_digito[u] = Move(u);
		dfs(u);
		Move(v);
	}
 
}
 
long long Ioi(int N, int M, int A[], int B[], int P, int V, int T) {
 
	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}
 
	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);
 
	memset(relevante,0,sizeof(relevante));
	for(int i : tree[P]) relevante[i] = 1;
	qual_digito[P] = V;
	dfs(P);
 
	long long ans = 0;
	for(int i = 0;i<MAXL;i++) if(digito[i]) ans += (1LL << i);
  
	return ans;
 
}

Joi.cpp

// Ivan Carvalho
// Amusement Park - JOI Open 2017
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 10011;
const int MAXL = 60;
 
static vector<int> grafo[MAXN],tree[MAXN],lista;
static bitset<MAXN> adjMat[MAXN];
static int digito[MAXL],pai[MAXN],contador[MAXN],idx[MAXN],relevante[MAXN];
 
static void bfs(){
 
	memset(contador,0,sizeof(contador));
	pai[0] = -1;
	contador[0] = 1;
	queue<int> fila;
	fila.push(0);
 
	while(!fila.empty()){
		int v = fila.front();
		fila.pop();
		lista.push_back(v);
		for(int u : grafo[v]){
			if(contador[u]) continue;
			contador[u] = 1;
			pai[u] = v;
			fila.push(u);
			adjMat[v][u] = 1;
			adjMat[u][v] = 1;
		}
	}
 
	memset(contador,0,sizeof(contador));
 
}
 
static void build_first(){
 
	vector<int> primeiro;
	for(int i = 0;i<MAXL;i++){
		primeiro.push_back(lista[i]);
		idx[primeiro.back()] = i;
	}
 
	for(int i : primeiro) tree[i] = primeiro;
 
}
 
static void extend_tree(int v){
 
	vector<int> copia = tree[pai[v]];
 
	for(int u : copia){
		for(int w : copia){
			if(adjMat[u][w] && u < w){
				contador[u]++;
				contador[w]++;
			}
		}
	}
 
	int achei = -1;
 
	for(int u : copia){
		if(u == pai[v]) continue;
		if(contador[u] == 1){
			achei = u;
			break;
		}
	}
 
	for(int u : copia){
		contador[u] = 0;
		if(u != achei) tree[v].push_back(u);
	}
 
	tree[v].push_back(v);
	idx[v] = idx[achei];
 
}
 
void Joi(int N, int M, int A[], int B[], long long X, int T){
	
	for(int i = 0;i<MAXL;i++){
		if(X & (1LL << i)) digito[i] = 1;
		else digito[i] = 0;
	}
 
	for(int i = 0;i<M;i++){
		grafo[A[i]].push_back(B[i]);
		grafo[B[i]].push_back(A[i]);
	}
 
	bfs();
	build_first();
	for(int i = MAXL;i<N;i++) extend_tree(lista[i]);

	for(int i = 0;i<N;i++) MessageBoard(i, digito[idx[i]] );
 
}