| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 270012 | AKaan37 | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Bismillahirrahmanirrahim
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█▄█
//█─█─█▄─█▄─█─█─█─█
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 5555;
const lo mod = 1000000007;
//~ vector<int> v;
int n,m,b[li],a[li],k,t,say,vis[li],mn[li],mx[li],mini,maxi,leaf,dep[li],visit[li],der,derin[li],leaff[li];
vector<int> vv,vect[5505];
inline void dfs(int node,int ata,int der){
int flag=0;
dep[node]=der;
for(int i=0;i<(int)vect[node].size();i++){
int go=vect[node][i];
if(go==ata)continue;
dfs(go,node,der+1);
flag=1;
//~ if(node==2)cout<<mn[go]<<endl;
if(mn[node]==0)mn[node]=mn[go];
else mn[node]=min(mn[node],mn[go]);
mx[node]=max(mx[node],mx[go]);
}
if(flag==0){vis[node]=++say;leaff[say]=node;}
if(flag==0)mn[node]=say;
if(flag==0)mx[node]=say;
//~ if(node==2)cout<<mn[2]<<"&&&&"<<endl;
}
vector<int> vec;
inline void push(int node,int ata){
if(mn[node]<=maxi && mx[node]>=mini)vec.pb(node);
for(int i=0;i<(int)vect[node].size();i++){
int go=vect[node][i];
if(go==ata)continue;
push(go,node);
}
}
inline void push1(int node,int ata){
//~ cout<<node<<"(())\n";
if(dep[node]<=der && visit[node]==0)vec.pb(node);
derin[dep[node]]=node;
for(int i=0;i<(int)vect[node].size();i++){
int go=vect[node][i];
if(go==ata)continue;
//~ cout<<mn[go]<<" : : "<<mx[go]<<" : : "<<go<<endl;
if(mn[go]>leaf || mx[go]<leaf)continue;
push1(go,node);
}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
say=0;
for(int i=1;i<=N;i++)vect[i].clear();
for(int i=1;i<=N;i++)visit[i]=0;
for(int i=1;i<=N;i++)mn[i]=0;
for(int i=1;i<=N;i++)mx[i]=0;
for(int i=1;i<=N;i++)leaff[i]=0;
for(int i=1;i<=N;i++)dep[i]=0;
for(int i=1;i<=N;i++)derin[i]=0;
for(int i=1;i<=N;i++)vis[i]=0;
for(int i=0;i<(int)bridges.size();i++){
int x=bridges[i].fi;
int y=bridges[i].se;
//~ cout<<x<<" : : "<<y<<endl;
vect[x].pb(y);
vect[y].pb(x);
}
//~ vv.clear();
//~ for(int i=1;i<=N;i++)if (query ({i})) return i;
dfs(1,0,0);
int bas=1;
int son=say;
while(bas<=son){
vec.clear();
mini=1;
maxi=ort;
push(1,0);
if(query(vec))son=ort-1;
else{
for(int i=0;i<(int)vec.size();i++)visit[vec[i]]=1;
bas=ort+1;
}
}
//~ cout<<bas<<endl;
leaf=bas;
bas=0;
son=dep[leaff[leaf]];
while(bas<=son){
vec.clear();
der=ort;
push1(1,0);
//~ for(int i=0;i<(int)vec.size();i++)printf("%d\n",vec[i]);
if(query(vec))son=ort-1;
else bas=ort+1;
//~ cout<<"\n"<<"\n";
}
//~ cout<<bas<<endl;
//~ cout<<vv[bas]<<endl;
if(bas>dep[leaff[leaf]])return 0;
return derin[bas];
}