# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1145997 | stasko | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <grader.h>
using namespace std;
int used[1024];
vector <int> v[1024];
vector <int> ans;
void dfs(int i)
{
used[beg]=1;
int sz=v[i].size();
ans.push_back(beg);
for(int j=0; j<sz; j++ )
{
if(!used[j])
{
dfs(j);
}
}
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
fill(used,used+1000,0);
ans.clear();
for(int i=1;i<=1010;i++)
{
v[i].clear();
}
for(auto c:bridges)
{
v[c.first].push_back(c.second);
v[c.second].push_back(c.first);
}
dfs(1);
int l=0;
int r=N-1;
int mid;
bool la;
while(l<r)
{
mid=(l+r)/2;
vector <int>k;
for(int i=0;i<=mid;i++)
{
k.push_back(ans[i]);
}
la=query(k);
if(la)
{
r=mid;
}
else l=mid+1;
}
//cout << l << endl;
return ans[r];
}