#include <bits/stdc++.h>
#include "grader.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define pii pair<int, int>
using namespace std;
const int NN = 513;
vector<pii> edges[NN];
vector<int> vv[NN];
int nn, used[NN];
void dfs(int u, int p = -1){
//cout<<u<<" ";
vv[u].pb(u);
for(auto x:edges[u]){
if(x.ff == p || used[x.ss]) continue;
dfs(x.ff, u);
for(auto xx:vv[x.ff]) vv[u].pb(xx);
}
}
int dfs_cc(int u, int p = -1){
pii mx = {-1, -1};
for(auto x:edges[u]){
if(used[x.ss] || x.ff == p) continue;
if(sz(vv[x.ff]) > mx.ff) mx.ff = sz(vv[x.ff]), mx.ss = x.ff;
}
if(mx.ff * 2 >= nn) return dfs_cc(mx.ss, u);
return u;
}
int solve(int cur){
//for(int i=0;i<5;i++) cout<<used[i]<<" ";
//cout<<"\n";
for(int i=0;i<N;i++) vv[i].clear();
dfs(cur);
//cout<<nn<<" "<<cur<<" ";
if(nn == 1) return 0;
int centr = dfs_cc(cur);
//cout<<"\n";
//cout<<cur<<" "<<centr<<"\n";
for(int i=0;i<N;i++) vv[i].clear();
dfs(centr);
//cout<<"\n";
//cout<<centr<<"\n";
vector<pair<int, pii>> childs;
for(auto x:edges[centr]) childs.pb({sz(vv[x.ff]), x});
sort(childs.begin(), childs.end());
//cout<<centr<<"\n";
//for(auto x:childs) cout<<x.ss.ff<<" "<<x.ff<<"\n";
//cout<<"______\n";
vector<int> qq = vv[childs.back().ss.ff];
qq.pb(centr);
vector<int> uu(N, 0);
uu[childs.back().ss.ss] = 1;
childs.pop_back();
int last = sz(qq);
int nw = -1;
int start;
for(auto x:childs){
nw = x.ff + last;
if(abs(nw*2 - nn) < abs(nn - last*2)){
for(auto xx : vv[x.ss.ff]) qq.pb(xx);
}else { start = x.ss.ff; break; }
uu[x.ss.ss] = 1;
}
for(auto &x:qq) x += 1;
int res = query(qq);
//for(auto x:qq) cout<<x<<" ";
//cout<<"\n";
if(nn == 2 && res){
int bb = qq.back(); qq.pop_back();
if(query({bb})) return bb-1;
return qq.back()-1;
}
if(res){
for(auto x:edges[centr]){
//cout<<uu[x.ss]<<" "<<x.ss<<"\n";
if(uu[x.ss]) continue;
else used[x.ss] = 1;
}
nn = sz(qq);
if(nn == 1) return centr;
return solve(centr);
}else{
for(auto x:edges[centr]){
if(uu[x.ss]) used[x.ss] = 1;
}
nn = (nn - sz(qq));
if(nn == 1) return start;
nn++;
return solve(centr);
}
return 0;
}
int findEgg (int N, vector < pair < int, int > > bridges){
memset(used, 0, sizeof used);
for(int i=0;i<NN;i++) edges[i].clear(), vv[i].clear();
nn = N;
for(int i=0;i<sz(bridges);i++){
edges[bridges[i].ff-1].pb({bridges[i].ss-1, i});
edges[bridges[i].ss-1].pb({bridges[i].ff-1, i});
}
//nn = N;
//dfs(0);
return solve(0)+1;
}
Compilation message
eastereggs.cpp: In function 'int solve(int)':
eastereggs.cpp:45:16: error: 'N' was not declared in this scope
45 | for(int i=0;i<N;i++) vv[i].clear();
| ^
eastereggs.cpp:55:16: error: 'N' was not declared in this scope
55 | for(int i=0;i<N;i++) vv[i].clear();
| ^
eastereggs.cpp:69:17: error: 'N' was not declared in this scope; did you mean 'NN'?
69 | vector<int> uu(N, 0);
| ^
| NN
