#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include "grader.h"
using namespace std;
void init(set<int> & islandsLeft, vector <pair<int,int>> & bridges, vector<vector<int>> & adj) {
int N = (int) bridges.size()+1;
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);
}
}
}
vector<int> process(set<int> & curQ, set<int> & islandsLeft) {
vector<int> queryVec, nextIs;
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);
}
}
return nextIs;
}
int findEgg(int N, vector <pair<int,int>> bridges) {
vector<vector<int>> adj(N);
vector<int> nextIs;
set<int> islandsLeft, curQ;
init(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.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
nextIs = process(curQ, islandsLeft);
islandsLeft.clear();
for (int is: nextIs) {
islandsLeft.insert(is);
//cout << is << ' ';
}
//cout << '\n';
}
return *islandsLeft.begin() + 1;
}
| # |
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 |
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 |
- |
