# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
483643 | 2021-10-31T12:40:16 Z | alexdumitru | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> #include "grader.h" using namespace std; vector<int> g[550]; int p[550]; bool query(vector < int > v); void dfs(int nod=1, int t=0) { int n=0; p[++n]=nod; for(auto i:g[nod])if(i!=t)dfs(i,nod); } bool qq(int poz) { vector<int> qqq; for(int i=1;i<=poz;i++)qqq.push_back(p[i]); return query(qqq); } int findEgg(int N, vector<pair<int,int> > bridges) { int st=1,dr=N-1,m,poz=N; for(auto i:bridges) { g[i.first].push_back(i.second); g[i.second].push_back(i.first); } dfs(); while(st<=dr) { m=st+(dr-st)/2; if(qq(m)) { poz=m; dr=m-1; } else st=m+1; } return p[poz]; }