oj.uz

Submission #576012

# Submission time Handle Problem Language Result Execution time Memory
576012 2022-06-12T04:40:17 Z I_am_balancing Easter Eggs (info1cup17_eastereggs) C++17
66 / 100
 17 ms 356 KB 
#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);
        //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);
}

Compilation message

eastereggs.cpp: In lambda function:
eastereggs.cpp:58:23: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   58 |             if(query({v}))return v;
      |                       ^
eastereggs.cpp:58:23: warning: narrowing conversion of 'v' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
eastereggs.cpp:100:5: warning: control reaches end of non-void function [-Wreturn-type]
  100 |     };
      |     ^

Subtask #1
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 208 KB Number of queries: 5
2 Partially correct 1 ms 208 KB Number of queries: 6
3 Partially correct 1 ms 208 KB Number of queries: 9
4 Partially correct 1 ms 208 KB Number of queries: 5

Subtask #2
26.4 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 336 KB Number of queries: 9
2 Partially correct 11 ms 336 KB Number of queries: 18
3 Partially correct 11 ms 336 KB Number of queries: 14
4 Partially correct 14 ms 336 KB Number of queries: 36

Subtask #3
13.2 / 20.0

# Verdict Execution time Memory Grader output
1 Partially correct 17 ms 336 KB Number of queries: 10
2 Partially correct 11 ms 356 KB Number of queries: 16
3 Partially correct 12 ms 336 KB Number of queries: 14
4 Partially correct 17 ms 336 KB Number of queries: 38