#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
int n;
vector<int> con[520];
vector<int> forniv[520];
int level[520];
bool visited[520];
int parent[520];
int rez=-1;
int mxmniv=0;
int root;
int cntq;
map<vector<int>,int> done;
bool fa_query(vector<int> cv)
{
if(done[cv]==0)
{
cntq--;
bool bl = query(cv);
if(bl==0)
done[cv]=-1;
else
done[cv]=1;
}
if(done[cv]==-1)
return 0;
return 1;
}
void dfs(int nod)
{
visited[nod]=1;
mxmniv = max(mxmniv, level[nod]);
forniv[level[nod]].push_back(nod);
for(auto adj:con[nod])
{
if(!visited[adj])
{
level[adj] = level[nod]+1;
parent[adj]=nod;
dfs(adj);
}
}
}
vector<int> aux;
int pls=1;
void dfs3(int nod, int dist)
{
pls=max(pls,dist);
visited[nod]=1;
for(auto adj:con[nod])
{
if(!visited[adj])
dfs3(adj,dist+1);
}
}
int find_root()
{
int mnm=n+2,care;
for(int i=1;i<=n;i++)
{
for(int i=1;i<=n;i++)
visited[i]=0;
pls=1;
dfs3(i,1);
if(pls<mnm)
{
mnm=pls;
care=i;
}
}
return care;
}
vector<int> bfsorder;
void bfs()
{
deque<int> dq;
dq.push_back(root);
while(!dq.empty())
{
int nod = dq.front();
dq.pop_front();
bfsorder.push_back(nod);
for(auto adj:con[nod])
if(!visited[adj])
dq.push_back(adj);
}
}
int fr[520];
bool verif3(int poz)
{
aux.clear();
for(int i=1;i<=n;i++)
fr[i]=0;
for(int i=0;i<=poz;i++)
{
int cur=bfsorder[i];
while(cur!=-1)
{
fr[cur]++;
cur = parent[cur];
}
}
for(int i=1;i<=n;i++)
{
if(fr[i]>0)
aux.push_back(i);
}
return fa_query(aux);
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
mt19937 rng(time(nullptr));
n=N;
if(n<=16)
cntq = 4;
else if(n<=500)
cntq = 9;
else
cntq = 9;
done.clear();
for(int i=1;i<=N;i++)
{
visited[i]=0;
con[i].clear();
forniv[i].clear();
}
rez=-1;
mxmniv=0;
for(auto x:bridges)
{
con[x.first].push_back(x.second);
con[x.second].push_back(x.first);
}
root = find_root();
level[root] = 1;
parent[root] = -1;
for(int i=1;i<=n;i++)
visited[i]=0;
dfs(root);
for(int i=1;i<=n;i++)
visited[i]=0;
bfs();
int st,dr,mij=0;
st=0;
dr=n-1;
while(st<=dr)
{
if(st==dr)
return bfsorder[st];
mij=(st+dr)/2;
if(verif3(mij) && (mij==0 || !verif3(mij-1)))
return bfsorder[mij];
else if(verif3(mij))
dr=mij-1;
else
st=mij+1;
}
return bfsorder[mij];
}
Compilation message
eastereggs.cpp: In function 'bool fa_query(std::vector<int>)':
eastereggs.cpp:21:19: error: 'query' was not declared in this scope; did you mean 'fa_query'?
21 | bool bl = query(cv);
| ^~~~~
| fa_query
