oj.uz

답안 #384733

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384733 2021-04-02T06:45:25 Z BlancaHM Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 39 ms 492 KB 
#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.0 / 40.0

# 결과 실행 시간 메모리 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

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 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

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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