#include <bits/stdc++.h>
#include "grader.h"
#define MOD 1000000007
#define INF 1061109567
#define pb push_back
#define in(s) freopen(s,"r",stdin);
#define out(s) freopen(s,"w",stdout);
#define fi first
#define se second
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
#define fa(i,x) for (auto i:x)
using namespace std;
const int N=515;
int sz[N],par[N];
vector<int> v,G[N];
void dfs(int u,int p,bool pushed) {
sz[u]=1;
fa (v,G[u]) if (v!=p) {
dfs(v,u);
par[v]=u;
sz[u]+=sz[v];
}
if (pushed) v.pb(u);
}
int cen(int u,int p,int cur) {
fa (v,G[u]) if (v!=p) {
if (sz[v]*2>=cur) return cen(v,u,cur);
}
return u;
}
int ask(int u,int p) {
v.clear();
dfs(u,p,0);
int tmp=cen(u,p,sz[u]);
dfs(tmp,par[tmp],1);
if (v.size()==1) return v[0];
bool temp=query(v);
if (tmp) return ask(tmp,par[tmp]);
else return ask(par[tmp],tmp);
}
int findEgg(int n,vector<pair<int,int>> bridges) {
fa (i,bridges) {
i.fi--; i.se--;
G[i.fi].pb(i.se);
G[i.se].pb(i.fi);
}
/*
Pick a centroid - like center for the tree. Now ask on its subtree. If the egg exists inside
then go for it. Else, go back up to the center.
*/
memset(used,false,sizeof(used));
cout<<ask(0,-1);
}
Compilation message
eastereggs.cpp: In function 'void dfs(int, int, bool)':
eastereggs.cpp:20:10: error: too few arguments to function 'void dfs(int, int, bool)'
dfs(v,u);
^
eastereggs.cpp:17:6: note: declared here
void dfs(int u,int p,bool pushed) {
^~~
eastereggs.cpp: In function 'int ask(int, int)':
eastereggs.cpp:38:7: warning: unused variable 'temp' [-Wunused-variable]
bool temp=query(v);
^~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:52:9: error: 'used' was not declared in this scope
memset(used,false,sizeof(used));
^~~~
eastereggs.cpp:52:9: note: suggested alternative: 'se'
memset(used,false,sizeof(used));
^~~~
se
eastereggs.cpp:54:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
