# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1128271 | enzy | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int maxn=514;
vector<int>v[maxn];
int pre[maxn], lin[maxn], tmp;
void dfs(int u){
tmp++;
pre[u]=tmp;
for(auto viz : v[u]){
if(pre[viz]) continue;
dfs(viz);
}
}
bool check(int x){
vector<int>ask;
for(int i=1;i<=x;i++) ask.push_back(lin[i]);
return query(ask);
}
int findEgg (int N,vector<pair<int,int>> bridges){
for(auto p : bridges){
v[p.first].push_back(p.second);
v[p.second].push_back(p.first);
}
dfs(1);
for(int i=1;i<=n;i++) lin[pre[i]]=i;
int l=1, r=n;
while(l<r){
int mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid+1;
}
return lin[l];
}