| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1317396 | brianabcr | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector <int> g[520];
int v[520], lvl[520];
void dfs (int nod, int t = 0, int depth)
{
lvl[nod] = depth;
for (auto it : g[nod])
{
if (it != t)
dfs (it, nod, depth + 1);
}
}
bool cmp (int a, int b)
{
return lvl[a] < lvl[b];
}
int findEgg (int n, vector < pair < int, int > > bridges)
{
for (int i = 0; i < bridges.size(); i++)
{
int x = bridges[i].first;
int y = bridges[i].second;
g[x].push_back (y);
g[y].push_back (x);
}
int k = 0;
for (int i = 1; i <= n; i++)
v[++k] = i;
dfs(1, 0, 1);
sort(v+1, v + n + 1, cmp);
int st = 1, dr = n;
while (st <= dr)
{
int mij = (st + dr) / 2;
vector <int> q;
for (int i = 1; i <= mij; i++)
q.push_back(v[i]);
int x = query(q);
if (x)
dr = mij;
else
st = mij + 1;
}
return st;
}
