# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1146207 | rado15 | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <grader.h>
#define endl '\n'
#define int long long int
using namespace std;
const int maxn = 600;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
vector<int> v[maxn];
bool used[maxn];
vector<int> topo;
void DFS(int beg)
{
used[beg] = true;
topo.push_back(beg);
for(auto &nb: v[beg])
{
if(!used[nb])
{
DFS(nb);
}
}
}
int findEgg(int n, pair<int, int> bridges)
{
memset(used, false, sizeof(used));
for(int i = 1; i <= n; i++)
{
v[i].clear();
}
for(int i = 0; i < n; i++)
{
int x, y;
x = bridges[i].first;
y = bridges[i].second;
v[x].push_back(y);
v[y].push_back(x);
}
topo.clear();
DFS(1);
int l = 0, r = n-1, mid;
vector<int> curr;
while(l < r)
{
mid = l + (r - l)/2;
curr.clear();
for(int i = 0; i <= m ; i++)
{
curr.push_back(topo[i]);
}
int q = query(curr);
if(q == 1)
{
r = mid;
}
else l = mid + 1;
}
return topo[l];
}