oj.uz

Submission #576024

# Submission time Handle Problem Language Result Execution time Memory
576024 2022-06-12T05:22:58 Z I_am_balancing Easter Eggs (info1cup17_eastereggs) C++17
0 / 100
 20 ms 476 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);
        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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 208 KB Number of queries: 4
2 Partially correct 1 ms 208 KB Number of queries: 5
3 Runtime error 1 ms 464 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 336 KB Number of queries: 8
2 Runtime error 3 ms 464 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 336 KB Number of queries: 9
2 Runtime error 3 ms 476 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -