| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 576009 | I_am_balancing | 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.
int findEgg(int n, vector<pair<int,int>> bridges){
using ll = long long;
vector<vector<ll>> g(n+1);
vector<ll> ban(n+1),sub(n+1);
ll crsz = n;
for(auto[a,b] : bridges)g[a].pb(b),g[b].pb(a);
function<void(ll,ll)> cnt = [&](ll v, ll p){
sub[v] = 1;
for(ll to : g[v]){
if(to == p || ban[to])continue;
cnt(to,v);
sub[v]+=sub[to];
}
};
function<ll(ll,ll)> findCentroid = [&](ll v, ll p){
for(ll to : g[v]){
if(to == p || ban[to])continue;
if(sub[to] > crsz/2)return findCentroid(to,v);
}
return v;
};
vector<int> csub;
function<void(ll,ll)> cS = [&](ll v, ll p){
csub.pb(v);
for(ll to : g[v]){
if(to == p || ban[to]){
cout << "rejected : " << v << " -> " << to << ' ' << ban[to] << ' ' << p << '\n';
continue;
}
cS(to,v);
}
};
function<ll(ll)> centr = [&](ll v){
cnt(v,0);
crsz = sub[v];
if(sub[v] == 1)return v;
if(sub[v] == 2){
if(query({v}))return v;
else{
for(ll to : g[v]){
if(ban[to])continue;
return to;
}
}
}
v = findCentroid(v,0);
cout << "Centroid: " << v << '\n';
ll l = 1, r = 0;
for(ll to : g[v]){
if(ban[to])continue;
r++;
}
while(r-l+1>1){
ll mid = (l+r)>>1;
ll t = 0;
for(ll to : g[v]){
if(ban[to])continue;
t++;
if(l<=t && t<=mid)cS(to,v);
}
csub.pb(v);
if(query(csub)){
r = mid;
}
else l = mid+1,ban[v]=1;
csub.clear();
}
ll t = 0;
for(ll to : g[v]){
if(ban[to])continue;
t++;
if(t != r){
ban[to]=1;
}
}
for(ll to : g[v]){
if(ban[to])continue;
return centr(to);
}
};
return centr(1);
}