#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int n;
vector<int> con[520];
vector<int> children[520];
vector<int> forniv[520];
int level[520];
bool visited[520];
int parent[520];
int rez=-1;
int mxmniv=0;
int root;
int cntq;
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);
for(int i=0;i<children[adj].size();i++)
children[nod].push_back(children[adj][i]);
}
}
children[nod].push_back(nod);
}
vector<int> aux;
void dfs2(int nod, int niv)
{
visited[nod]=1;
aux.push_back(nod);
for(auto adj:con[nod])
{
if(!visited[adj] && level[adj]<=niv)
{
dfs2(adj, niv);
}
}
}
bool verif_nivel(int niv)
{
for(int i=1;i<=n;i++)
visited[i]=0;
aux.clear();
dfs2(root,niv);
cntq--;
return query(aux);
}
int find_nivel()
{
int st,dr,mij;
st=1;
dr=mxmniv;
while(st<=dr)
{
if(st==dr)
return st;
mij=(st+dr)/2;
if(verif_nivel(mij))
dr=mij;
else
st=mij+1;
}
return mij;
}
int fr[520];
bool verif_interval(int le, int ri, int niv)///returneaza 1 daca oul se afla in nodurile de pe forniv[niv][le..ri]
{
aux.clear();
for(int i=1;i<=n;i++)
fr[i]=0;
for(int i=le;i<=ri;i++)
{
int cur=forniv[niv][i];
while(cur!=-1)
{
fr[cur]++;
cur = parent[cur];
}
}
for(int i=1;i<=n;i++)
{
if(fr[i]>0)
aux.push_back(i);
}
cntq--;
return 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;
for(int i=1;i<=N;i++)
{
visited[i]=0;
con[i].clear();
children[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=(rng()%n)+1;
level[root] = 1;
parent[root] = -1;
dfs(root);
int niv = find_nivel();
int st,dr,mij=0;
st=0;
dr=forniv[niv].size()-1;
while(st<=dr)
{
if(st==dr)
return forniv[niv][st];
if(dr-st+1<=cntq)
{
for(int i=st;i<=dr;i++)
{
if(query({forniv[niv][i]}))
return forniv[niv][i];
}
}
mij=(st+dr)/2;
if(verif_interval(st,mij,niv))
dr=mij;
else
st=mij+1;
}
return forniv[niv][mij];
}
Compilation message
eastereggs.cpp: In function 'void dfs(int)':
eastereggs.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for(int i=0;i<children[adj].size();i++)
| ~^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int find_nivel()':
eastereggs.cpp:60:15: warning: 'mij' may be used uninitialized in this function [-Wmaybe-uninitialized]
60 | int st,dr,mij;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
336 KB |
Number of queries: 5 |
| 2 |
Partially correct |
1 ms |
336 KB |
Number of queries: 6 |
| 3 |
Partially correct |
1 ms |
336 KB |
Number of queries: 5 |
| 4 |
Partially correct |
1 ms |
336 KB |
Number of queries: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
552 KB |
Number of queries: 9 |
| 2 |
Partially correct |
8 ms |
400 KB |
Number of queries: 10 |
| 3 |
Partially correct |
18 ms |
432 KB |
Number of queries: 12 |
| 4 |
Partially correct |
11 ms |
404 KB |
Number of queries: 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
43 ms |
864 KB |
Number of queries: 10 |
| 2 |
Partially correct |
13 ms |
336 KB |
Number of queries: 11 |
| 3 |
Partially correct |
18 ms |
444 KB |
Number of queries: 11 |
| 4 |
Partially correct |
13 ms |
336 KB |
Number of queries: 12 |
