oj.uz

Submission #471219

# Submission time Handle Problem Language Result Execution time Memory
471219 2021-09-07T16:49:21 Z BlancaHM Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 42 ms 500 KB 
#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm>
#include <set>
#include <queue>
#include "grader.h"
using namespace std;

void reset(set<int> & possibleLocations, vector<pair<int, int>> & edges, vector<vector<int>> & adjList) {
	int N = (int) edges.size() + 1;
	adjList = vector<vector<int>>(N);
	for (int i = 0; i < N; i++)
		possibleLocations.insert(i); // We add the island to the remaining possibilities
    for (int i = 0; i < N-1; i++) {
        // We add the edge to the adjacency list
        adjList[edges[i].first - 1].push_back(edges[i].second - 1);
        adjList[edges[i].second - 1].push_back(edges[i].first - 1);
	}
}

// Query about the selected half and discard the appropriate half after the query response
set<int> reduceRemaining(set<int> & currentSelection, set<int> & possibleLocations) {
	vector<int> queryIslands;
	set<int> nextPossibleLocations;

	for (auto it = currentSelection.begin(); it != currentSelection.end(); it++)
		queryIslands.push_back(*it + 1);

	if (query(queryIslands) == 1) {
		// selectedIslands = intersection of possibleLocations and currentSelection
		for (int island: possibleLocations)
			if (currentSelection.find(island) != currentSelection.end())
				nextPossibleLocations.insert(island);
	} else {
		// selectedIslands = intersection of possibleLocations and NOT currentSelection
		for (int island: possibleLocations)
			if (currentSelection.find(island) == currentSelection.end())
				nextPossibleLocations.insert(island);
	}

	return nextPossibleLocations;
}

set<int> selectHalf(set<int> & possibleLocations, vector<vector<int>> & adjList) {
    int root = *possibleLocations.begin();

    // Do BFS starting on the root until we have selected half of the possible egg locations
    // Note: as the islands in the query must be connected, we may include in the query other islands which we know do not contain the egg
    queue<int> Q;
	Q.push(root);

    int selectedIslands = 1; // Number of islands selected which are possible egg locations
    int possibleIslands = (int) possibleLocations.size();

    set<int> currentSelection; // Islands selected for the next query, including previously discarded ones
    currentSelection.insert(root);

    while (!Q.empty()) {
        if (selectedIslands * 2 >= possibleIslands)
            break; // We already have 1/2 of the possible egg locations

        // Otherwise, continue with the DFS
        int currentIsland = Q.front();
        Q.pop();

        // Iterate over the neighbouring islands
        for (int neighbour : adjList[currentIsland]) {
            if (selectedIslands * 2 >= possibleIslands)
                break;
            if (currentSelection.find(neighbour) == currentSelection.end()) {
                // Have not selected this island for the query yet-> we select it
                currentSelection.insert(neighbour);
                Q.push(neighbour);
                if (possibleLocations.find(neighbour) != possibleLocations.end())
                    selectedIslands++; // this island is a possible egg location
            }
        }
    }
    return currentSelection;
}

int findEgg(int N, vector<pair<int, int>> edges) {
	vector<vector<int>> adjList;
	set<int> possibleLocations, currentSelection;
	reset(possibleLocations, edges, adjList);
	queue<int> Q;
	while((int) possibleLocations.size() > 1) {
        currentSelection = selectHalf(possibleLocations, adjList);
		// Process our current selection, reducing the possible locations set to 1/2 its previous size
		possibleLocations = reduceRemaining(currentSelection, possibleLocations);
	}
	return *possibleLocations.begin() + 1;
}

Subtask #1
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Number of queries: 4
2 Correct 1 ms 200 KB Number of queries: 4
3 Correct 1 ms 200 KB Number of queries: 4
4 Correct 2 ms 200 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 328 KB Number of queries: 8
2 Correct 26 ms 328 KB Number of queries: 9
3 Correct 36 ms 384 KB Number of queries: 9
4 Correct 33 ms 368 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 340 KB Number of queries: 9
2 Correct 37 ms 308 KB Number of queries: 9
3 Correct 42 ms 328 KB Number of queries: 9
4 Correct 39 ms 500 KB Number of queries: 9