Submission #1319714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319714		hssaan_arif	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	2 ms	584 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

#define pb push_back
// #define int long long
#define fi first
#define se second

const int N1 = 3e5 + 5, M = 1e9 + 7, LG = 20;

int n , A[N1] , x , mo , ANS = -1;
vector<int> lis[N1] , up;
bool vi[N1];


void dfs(int v , int par , int N){
    if (ANS >= 0) return;

    up.pb(v);
    mo--;

    if (mo <= 0){
        bool x = query(up);
        // cout << v << ' ' << x << endl;

        if (x){
            vector<int> p;

            for (int i : up){
                
                if (!vi[i]){
                    p.pb(i);
                    // cout << i << ' ';
                }
            }
            // cout << endl;
           
            int l = 0 , r = p.size();

            while(l + 1 < r){
                int mid = (l+r)/2;

                vector<int> k;

                for (int i=mid ; i<r ; i++){
                    k.pb(p[i]);
                }

                bool x = query(k);

                if (x){
                    l = mid;
                }else{
                    r = mid;
                }
            }

            ANS = p[l];
            // cout << l << endl;
            return;
        }else{
            for (int i : up) vi[i] = 1;

            mo = N/2;
            N -= mo;
            
            // cout << "Don " << mo << endl;
            
        }
    }
    

    for (int u : lis[v]){
        if (u==par) continue;
        dfs(u , v , N);
    }
}

int findEgg (int N, vector < pair < int, int > > bridges)
{

    for (int i=0 ; i<=N ; i++){
        vi[i] = 0;
        lis[i].clear();
    }

    for (int i=0 ; i<N-1 ; i++){
        lis[bridges[i].fi].pb(bridges[i].se);
        lis[bridges[i].se].pb(bridges[i].fi);
    }

    if (N == 1){
        return 1;
    }

    if (N == 2){
        bool x = query({1});
        if (x) return 1;
        else return 2;
    }



    mo = N/2;
    ANS = -1;
    up.clear();
    
    // f = 4;
    // cout << N << endl;
    dfs(1 , 0 , N - N/2);
    // cout << ANS << endl;

    return ANS;
}

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