#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm>
#include <set>
#include <queue>
#include "grader.h"
using namespace std;
void inicializar(set<int> & posibilidadesHuevo, vector<pair<int, int>> & aristas, vector<vector<int>> & listaAdyacencia) {
int N = (int) aristas.size() + 1;
listaAdyacencia = vector<vector<int>>(N);
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) == 1) {
// islasEnLaSeleccion = intersección de posibilidadesHuevo y seleccionActual
for (int is : posibilidadesHuevo) {
if (seleccionActual.find(is) != seleccionActual.end())
siguienteSeleccion.push_back(is);
}
} else {
// islasEnLaSeleccion = intersección de posibilidadesHuevo 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) {
vector<vector<int>> listaAdyacencia;
set<int> posibilidadesHuevo, seleccionActual;
inicializar(posibilidadesHuevo, aristas, listaAdyacencia);
queue<int> cola;
while((int) posibilidadesHuevo.size() > 1) {
seleccionActual = set<int>();
seleccionActual.insert(*posibilidadesHuevo.begin());
cola = queue<int>();
cola.push(*posibilidadesHuevo.begin());
int islasEnLaSeleccion = 1;
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 |
492 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 |
9 ms |
364 KB |
Number of queries: 8 |
| 2 |
Correct |
26 ms |
364 KB |
Number of queries: 9 |
| 3 |
Correct |
40 ms |
364 KB |
Number of queries: 9 |
| 4 |
Correct |
35 ms |
364 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
364 KB |
Number of queries: 9 |
| 2 |
Correct |
39 ms |
364 KB |
Number of queries: 9 |
| 3 |
Correct |
38 ms |
364 KB |
Number of queries: 9 |
| 4 |
Correct |
39 ms |
364 KB |
Number of queries: 9 |
