//#include <bits/stdc++.h>
#include "grader.h"
#define X first
#define Y second
using namespace std;
vector<int> g[530];
vector<int> half;
vector<int> all;
vector<int> help;
int have;
bool took[530];
/*
int egg;
bool query(vector< int > v){
for(int x : v)
if(x == egg)
return true;
return false;
}
*/
void findHalf(int x){
if(have == 0)
return;
took[x] = true;
half.push_back(x);
have--;
for(int y : g[x]){
if(took[y] == true)
continue;
findHalf(y);
}
}
int findEgg (int N, vector< pair< int, int > > graf ){
memset(took, 0, sizeof(took));
for(int i = 0; i <= N; i++)
g[i].clear();
for(int i = 0; i < N - 1; i++){
int x = graf[i].X;
int y = graf[i].Y;
g[x].push_back(y);
g[y].push_back(x);
if(!took[x]){
all.push_back(x);
took[x] = true;
}
if(!took[y]){
all.push_back(y);
took[y] = true;
}
}
memset(took, false, sizeof(took));
while(all.size() > 1){
have = N / 2;
half.clear();
findHalf(all[0]);
bool ans = query(half);
if(ans){
N /= 2;
}
else{
N = N - N / 2;
}
help.clear();
for(int x : all){
if(took[x] == ans)
help.push_back(x);
}
all.clear();
for(int x : help){
took[x] = false;
all.push_back(x);
}
}
return all[0];
}
/*
int main(){
int m;
cout << "num. of nodes\n";
cin >> m;
cout << "easter egg\n";
cin >> egg;
vector< pair<int, int> > inp;
for(int i = 0; i < m - 1; i++){
int a, b;
cin >> a >> b;
inp.push_back({a, b});
}
cout << findEgg(m, inp);
return 0;
}
Compilation message
eastereggs.cpp:98:1: error: unterminated comment
98 | /*
| ^
