| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 384459 | 2021-04-01T17:23:01 Z | BlancaHM | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KB |
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
int findEgg(int N, vector <pair<int,int>> bridges) {
vector<vector<int>> adj(N);
vector<int> queryVec, nextIs;
set<int> islandsLeft, curQ;
for (int i = 0; i < N; i++) {
islandsLeft.insert(i);
if (i) {
bridges[i-1].first--;
bridges[i-1].second--;
adj[bridges[i-1].first].push_back(bridges[i-1].second);
adj[bridges[i-1].second].push_back(bridges[i-1].first);
}
}
queue<int> q;
while ((int) islandsLeft.size() > 1) {
// hacemos un árbol que contenga la primera mitad de islas restantes y ninguna de la segunda mitad
curQ.clear();
curQ.insert(*islandsLeft.begin());
q = queue<int>();
q.push(*islandsLeft.begin());
int islands = 1;
while(q.size()) {
if (islands*2 >= (int) islandsLeft.size())
break;
int curIs = q.front();
for (int v: adj[curIs]) {
if (islands*2 >= (int) islandsLeft.size()) break;
if (curQ.find(v) == curQ.end()) {
curQ.insert(v);
q.push(v);
if (islandsLeft.find(v) != islandsLeft.end())
islands++;
}
}
if (islands*2 >= (int) islandsLeft.size()) break;
}
// process islandsLeft
queryVec.clear();
for (auto it = curQ.begin(); it != curQ.end(); it++)
queryVec.push_back(*it);
if (query(queryVec)) {
// islands = intersection of islands and curQ
nextIs.clear();
for (int is: islandsLeft) {
if (curQ.find(is) != curQ.end())
nextIs.push_back(is);
}
} else {
// islands = intersection of islands and NOT curQ
nextIs.clear();
for (int is: islandsLeft) {
if (curQ.find(is) == curQ.end())
nextIs.push_back(is);
}
}
islandsLeft.clear();
for (int is: nextIs)
islandsLeft.insert(is);
}
return *islandsLeft.begin();
}