#include <bits/stdc++.h>
using namespace std;
extern int query(vector<int> islands);
int findEgg(int n,vector<pair<int,int>>bridges){
vector<vector<int>>tree(n+1);
for(auto &[u,v] : bridges){
tree[u].push_back(v);
tree[v].push_back(u);
}
queue<int>q;
vector<int>pr(n+1,-1);
vector<bool>col(n+1,false);
q.push(1);
col[1]=true;
while (!q.empty()) {
int node=q.front();
q.pop();
for(int neig : tree[node]) {
if(!col[neig]) {
col[neig]=true;
pr[neig]=node;
q.push(neig);
}
}
}
vector<int>res;
for(int i=1;i<=n;++i) {
res.push_back(i);
}
while(res.size()>1) {
int mid=res.size()/2;
vector<int>ll(res.begin(),res.begin()+mid);
vector<int>rr(res.begin()+mid,res.end());
if (query(ll)){
res=ll;
}
else {
res=rr;
}
}
return res[0];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |