#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;
}
Compilation message
eastereggs.cpp: In function 'std::set<int>& reduceRemaining(std::set<int>&, std::set<int>&)':
eastereggs.cpp:43:9: warning: reference to local variable 'nextPossibleLocations' returned [-Wreturn-local-addr]
43 | return nextPossibleLocations;
| ^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:26:11: note: declared here
26 | set<int> nextPossibleLocations;
| ^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'std::set<int>& selectHalf(std::set<int>&, std::vector<std::vector<int> >&)':
eastereggs.cpp:81:12: warning: reference to local variable 'currentSelection' returned [-Wreturn-local-addr]
81 | return currentSelection;
| ^~~~~~~~~~~~~~~~
eastereggs.cpp:57:14: note: declared here
57 | set<int> currentSelection; // Islands selected for the next query, including previously discarded ones
| ^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
328 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
