| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1348284 | ken | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
vector <int> edge[10040];
int tour[10040];
int rev[10040];
vector <int> ans;
//int query(vector < int > islands);
int cnt = 1;
void dfs(int id,int pa = -1){
rev[cnt] = id;
tour[id] = cnt++;
//cout << id << "\n";
for (auto ii : edge[id]){
if(ii == pa)continue;
dfs(ii,id);
}
}
bool ask(int til){
vector <int> smth;
for (int i=1; i<=til; i++){
smth.push_back(rev[i]);
}
return query(smth);
}
int findEgg(int N, vector<pair<int, int>> bridges){
for (auto [ft,sd] : bridges){
edge[ft].push_back(sd);
edge[sd].push_back(ft);
}
//ans.push_back(1);
dfs(1);
/*
for (int i=1; i<=N; i++){
cout << tour[i] << " " ;
}cout << "\n";
*/
for (int i=1; i<=N; i++){
cout << rev[i] << " " ;
}
int l=1,r=N;
while(l<r){
int mid = (l+r)/2;
if(ask(mid)){
r = mid;
}else{
l = mid+1;
}
}
return l;
}
/*
int main(){
int n,m;
cin >> n >> m;
vector <pair<int,int>> brid;
for (int i=1; i<=m; i++){
int ai,bi;
cin >> ai >> bi;
brid.push_back({ai,bi});
}
findEgg(n, brid);
}
*/