# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1130716 | nikolashami | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include"grader.h"
using namespace std;
const int N=515;
vector<int>g[N];
int tour[N],point,n;
void dfs(int u,int p){
tour[point++]=u;
for(int v:g[u]){
if(!(v^p))continue;
dfs(v,u);
}
}
vector<int>get(int x){
vector<int>ret;
for(int i=0;i<=x;++i)
ret.push_back(tour[i]);
return ret;
}
int findEgg(int N,vector<pair<int,int>>bridges){
n=N;
for(auto&[u,v]:bridges){
g[u].push_back(v);
g[v].push_back(u);
}
point=0;
dfs(1,0);
int l=0,r=n-1,ans=tour[n-1];
while(l<=r){
int m=(l+r)/2;
if(query(get(m))){
r=m-1;
ans=tour[m];
}else
l=m+1;
}
return ans;
}
signed main(){
cin>>n;
vector<pair<int,int>>vv;
for(int i=1,u,v;i<n;++i){
cin>>u>>v;
vv.push_back({u,v});
}
cout<<findEgg(n,vv);
}