#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
void dfs(int u, vector<vector<int>> &adj, vector<vector<int>> &path, vector<bool> &visit)
{
path[0].emplace_back(u);
path[path[0].size()] = path[0];
visit[u] = true;
for (auto v : adj[u])
{
if ((visit[v] == false))
{
dfs(v, adj, path, visit);
}
}
}
int findEgg(int N, vector<pair<int, int>> bridges)
{
vector<vector<int>> adj(515), path(515);
vector<bool> visit(513, false);
for (auto [u, v] : bridges)
{
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
dfs(1, adj, path, visit);
path[0].emplace_back(1);
int l = 1, mid, r = N;
// for (int i = 0; i <= N; i++)
// {
// for (auto v : path[i])
// {
// cout << v << " ";
// }
// cout << "\n";
// }
while (l < r)
{
int mid = l + (r - l) / 2;
if (query(path[mid]) == 1)
{
r = mid;
}
else
{
l = mid + 1;
}
}
return path[r].back();
// if (query ({1})) return 1;
// return N;
}
// int main()
// {
// cout << findEgg(5, {{1, 2}, {1, 3}, {2, 4}, {4, 5}});
// }
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |