| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 762195 | 2023-06-21T04:17:40 Z | salmon | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector <pair<int,int>> bridges){
set<int> notdone;
queue<int> q;
bool visited[1100];
vector<int> adjlst[1100];
vector<int> quer;
int goal;
for(int i = 1; i <= N; i++){
visited[i] = false;
adjlst[i].clear();
marked[i] = false;
notdone.insert(i);
}
quer.clear();
for(int i = 0; i < N - 1; i++){
adjlst[bridges[i].first].push_back(bridges[i].second);
adjlst[bridges[i].second].push_back(bridges[i].first);
}
while(notdone.size() != 1){
int sise = notdone.size();
goal = sise/2;
for(auto i : notdone){
bool flag = false;
if(sise != N){
for(int j : adjlst[i]){
if(notdone.find(i) == notdone.end()){
flag = true;
break;
}
}
}
if(flag){
q.push(i);
while(!q.empty()){
int i = q.front();
q.pop();
if(visited[i]) continue;
if(goal == 0) continue;
visited[i] = true;
goal--;
quer.push_back(i);
for(int j : adjlst[i]){
q.push(j);
}
}
}
}
/*printf("q: ");
for(auto i : quer){
printf("%d ",i);
}
printf("\n");*/
int con = quer.size();
if(query(quer)){
notdone.clear();
for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
//printf("%d ",quer[i]);
notdone.insert(quer[i]);
visited[quer[i]] = false;
quer.pop_back();
}
}
else{
for(int i = quer.size() - 1; i > con - 1 - sise/2; i--){
notdone.erase(quer[i]);
}
}
/*for(auto i : notdone){
printf("%d ",i);
}
printf("\n");*/
}
return (*notdone.begin());
}