oj.uz

답안 #386948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
386948 2021-04-07T16:38:38 Z BlancaHM Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 40 ms 492 KB 
#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;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

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

Subtask #3
20.0 / 20.0

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