#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int dfs(int cn, vector<int>&preorder, vector<vector<int>>&adjlist, int curr)
{
preorder[cn]=++curr;
for(int to:adjlist[cn])
{
if(preorder[to]!=0)continue;
curr=dfs(to,preorder,adjlist,curr);
}
return curr;
}
int findEgg (int N, vector<pair<int,int>>bridges)
{
int n=N;int curr=0;
vector<int>preorder(n+1,0);
vector<vector<int>>adjlist(n+1);
for(int a=0;a<(n-1);a++)
{
int t1=bridges[a].first,t2=bridges[a].second;
adjlist[t1].push_back(t2);
adjlist[t2].push_back(t1);
}
dfs(1,preorder,adjlist,curr);
int hi=n,lo=1,mid,ans;
while(hi>=lo)
{
mid=(hi+lo)/2;
vector<int>queset;
for(int a=lo;a<=mid;a++){queset.push_back(a);}
if(query(queset))
{
ans=mid;
hi=mid-1;
}
else
{
lo=mid+1;
}
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |