# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1145939 | ivailo_ganchev | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1024;
vector<int>e[MAXN];
vector<int>order;
int n;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
void dfs(int node, int parent)
{
order.push_back(node);
for(int &nb : e[node])
{
if(nb==parent)
continue;
dfs(nb, node);
}
}
bool check(int mid)
{
vector<int>q;
q.clear();
for(int i=0;i<=mid;i++)
{
q.push_back(order[i]);
}
int qAns=query(q);
return qAns;
}
int binarySearch()
{
int l=0,r=order.size()-1,mid;
while(l<=r)
{
mid=(l+r)/2;
if(check(mid))r=mid-1;
else l=mid+1;
}
return order[l];
}
void read(int N, vector < pair < int, int > > &bridges)
{
n=N;
for(pair <int , int>& i : bridges)
{
e[i.first].push_back(i.second);
e[i.second].push_back(i.first);
}
}
void clearMemory()
{
for(int i=0;i<MAXN;i++)
{
e[i].clear();
}
order.clear();
}
int findEgg (int N, vector<pair<int,int>>bridges)
{
read(N, bridges);
dfs(1, -1);
int ans=binarySearch();
clearMemory();
return ans;
}