Submission #384733

#	Time	Username	Problem	Language	Result	Execution time	Memory
384733		BlancaHM	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	39 ms	492 KiB

eastereggs

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include "grader.h"
using namespace std;

void init(set<int> & posibilidadesHuevo, vector <pair<int,int>> & aristas, vector<vector<int>> & listaAdyacencia) {
	int N = (int) aristas.size()+1;
	listaAdyacencia.clear();
	listaAdyacencia.assign(N, vector<int>());
	posibilidadesHuevo = set<int>();
	posibilidadesHuevo.clear();
	for (int i = 0; i < N; i++) {
		posibilidadesHuevo.insert(i); // añadimos la isla a las posibilidades restantes
		if (i) {
			// añadimos la arista a la lista de adyacencia
			int a = aristas[i-1].first - 1, b = aristas[i-1].second - 1;
			listaAdyacencia[a].push_back(b);
			listaAdyacencia[b].push_back(a);
		}
	}
}

vector<int> procesar(set<int> & seleccionActual, set<int> & posibilidadesHuevo) {
	// creamos un vector con la mitad seleccionada para poder hacer la pregunta
	vector<int> queryVec = vector<int>(), siguienteSeleccion = vector<int>();
	queryVec.clear();
	siguienteSeleccion.clear();
	for (auto it = seleccionActual.begin(); it != seleccionActual.end(); it++)
		queryVec.push_back(*it + 1);
	// hacemos la pregunta
	if (query(queryVec)) {
		// islasEnLaSeleccion = intersección de islasEnLaSeleccion y seleccionActual
		for (int is : posibilidadesHuevo) {
			if (seleccionActual.find(is) != seleccionActual.end())
				siguienteSeleccion.push_back(is);
		}
	} else {
		// islasEnLaSeleccion = intersección de islasEnLaSeleccion y NO seleccionActual
		for (int is : posibilidadesHuevo) {
			if (seleccionActual.find(is) == seleccionActual.end())
				siguienteSeleccion.push_back(is);
		}
	}
	return siguienteSeleccion;
}

int findEgg(int N, vector <pair<int,int>> aristas) {
	// inicializamos nuestras variables
	vector<vector<int>> listaAdyacencia;
	set<int> posibilidadesHuevo, seleccionActual;
	init(posibilidadesHuevo, aristas, listaAdyacencia);
	queue<int> cola;

	while ((int) posibilidadesHuevo.size() > 1) {
		// hacemos un árbol que contenga la primera mitad de islas restantes y ninguna de la segunda mitad
		// así, encontramos la isla del huevo con búsqueda binaria
		seleccionActual = set<int>();
		seleccionActual.clear();
		seleccionActual.insert(*posibilidadesHuevo.begin()); // vamos creando la selección empezando por un nodo arbitrario dentro de los restantes
		// la selección puede incluir islas ya descartadas, ya que igual no hay forma de conectar las islas restantes
		cola = queue<int>();
		cola.push(*posibilidadesHuevo.begin()); // lo añadimos a la cola (procesamos de manera similar al algoritmo de Prim)
		int islasEnLaSeleccion = 1; // número de islas en la selección sin contar islas ya descartadas
		while(!cola.empty()) {
			if (islasEnLaSeleccion*2 >= (int) posibilidadesHuevo.size())
				break; // ya tenemos la mitad de las islas seleccionadas -> no queremos más
			int islaActual = cola.front(); // en caso contrario, seleccionamos una isla del frente de la cola
			cola.pop(); // la quitamos de la cola
			for (int islaVecina: listaAdyacencia[islaActual]) {
				if (islasEnLaSeleccion*2 >= (int) posibilidadesHuevo.size()) break;
				if (seleccionActual.find(islaVecina) == seleccionActual.end()) {
					// no hemos seleccionado aún esta isla -> la añadimos
					seleccionActual.insert(islaVecina);
					cola.push(islaVecina);
					if (posibilidadesHuevo.find(islaVecina) != posibilidadesHuevo.end())
						islasEnLaSeleccion++; // no estaba descartada esta isla -> incrementamos el contador
				}
				if (islasEnLaSeleccion*2 >= (int) posibilidadesHuevo.size()) break;
			}
		}
		// procesamos nuestra selección para obtener la siguiente, quedándonos con la mitad
		vector<int> siguienteSeleccion = procesar(seleccionActual, posibilidadesHuevo);
		posibilidadesHuevo.clear();
		for (int isla: siguienteSeleccion)
			posibilidadesHuevo.insert(isla);
	}
	return *posibilidadesHuevo.begin() + 1;
}

• Subtask 1: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20