Submission #576024

#	Time	Username	Problem	Language	Result	Execution time	Memory
576024		I_am_balancing	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	20 ms	476 KiB

eastereggs

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using tl = tuple<ll,ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
#define sz(x) ll((x).size())
#define pb emplace_back
#define F first
#define S second
const ll inf = (1ll<<60);
const ll N = 1e5 + 100;
const ll K = 3;
const ld PI = 3.141592653589793238462643383279;
int query(vector < int > islands);

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);
        cnt(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 = 0,S = 0;
            ll t = 0;
            for(ll to : g[v]){
                if(ban[to])continue;
                t++;
                if(l<=t && t<=r)S+=sub[to];
            }
            S>>=1;t=0;
            //cout << l << ' ' << r << ' ' << S << '\n';
            sort(all(g[v]),[&](ll aa, ll bb){
                    return sub[aa] < sub[bb];
                 });
            for(ll to : g[v]){
                if(ban[to])continue;
                t++;
                if(l<=t && t<=r && S>0)cS(to,v),S-=sub[to],mid=t;
            }
            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 v;
    };
    return centr(1);
}

Compilation message (stderr)

eastereggs.cpp: In lambda function:
eastereggs.cpp:59:23: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   59 |             if(query({v}))return v;
      |                       ^
eastereggs.cpp:59:23: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20