#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Number of queries: 4 |
| 2 |
Correct |
2 ms |
364 KB |
Number of queries: 4 |
| 3 |
Correct |
2 ms |
364 KB |
Number of queries: 4 |
| 4 |
Correct |
2 ms |
364 KB |
Number of queries: 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
364 KB |
Number of queries: 8 |
| 2 |
Correct |
29 ms |
364 KB |
Number of queries: 9 |
| 3 |
Correct |
36 ms |
452 KB |
Number of queries: 9 |
| 4 |
Correct |
35 ms |
364 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
364 KB |
Number of queries: 9 |
| 2 |
Correct |
37 ms |
364 KB |
Number of queries: 9 |
| 3 |
Correct |
39 ms |
492 KB |
Number of queries: 9 |
| 4 |
Correct |
38 ms |
364 KB |
Number of queries: 9 |
