# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1139577 | tkm_algorithms | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
/**
* In the name of Allah
* We are nothing and you're everything
* author: najmuddin
**/
#include <bits/stdc++.h>
#include "grader.h"
#include "grader.cpp"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges) {
vector<int> g[520], obhod(520, -1);
int c = 0;
for (auto i: bridges) {
g[i.first].push_back(i.second);
g[i.second].push_back(i.first);
}
queue<pair<int, int>> q;
q.push({1, -1});
while (!q.empty()) {
auto u = q.front();
q.pop();
obhod[++c] = u.first;
for (auto i: g[u.first])
if (i != u.second)q.push({i, u.first});
}
int l = 0, r = N+1;
while (r-l>1) {
int mid = (l + r) >> 1;
assert(mid >=1 && mid <= N);
vector<int> a;
for (int i = 1; i <= mid; ++i)
a.push_back(obhod[i]);
if (query(a) == 1)r = mid;
else l = mid;
}
return obhod[r];
}