#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include "grader.h"
using namespace std;
/*
Variables:
islandsLeft
curQ
bridges
adj
queryVec
nextIs
q
*/
void reset(set<int> & islandsLeft, vector <pair<int,int>> & bridges, vector<vector<int>> & adj) {
int N = (int) bridges.size()+1;
adj.clear();
adj.assign(N, vector<int>());
islandsLeft = set<int>();
islandsLeft.clear();
for (int i = 0; i < N; i++) {
islandsLeft.insert(i);
if (i) {
int a = bridges[i-1].first - 1, b = bridges[i-1].second - 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
}
}
vector<int> process(set<int> & curQ, set<int> & islandsLeft) {
vector<int> queryVec = vector<int>(), nextIs = vector<int>();
queryVec.clear();
nextIs.clear();
for (auto it = curQ.begin(); it != curQ.end(); it++)
queryVec.push_back(*it);
if (query(queryVec)) {
// islands = intersection of islands and curQ
for (int is : islandsLeft) {
if (curQ.find(is) != curQ.end())
nextIs.push_back(is);
}
} else {
// islands = intersection of islands and NOT curQ
for (int is : islandsLeft) {
if (curQ.find(is) == curQ.end())
nextIs.push_back(is);
}
}
return nextIs;
}
int findEgg(int N, vector <pair<int,int>> bridges) {
vector<vector<int>> adj;
set<int> islandsLeft, curQ;
reset(islandsLeft, bridges, adj);
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 = set<int>();
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();
q.pop();
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
vector<int> nextIs = process(curQ, islandsLeft);
islandsLeft.clear();
for (int is: nextIs)
islandsLeft.insert(is);
}
return *islandsLeft.begin() + 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
620 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
