Submission #1145936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145936		bbbiros	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	516 KiB

eastereggs

#include <vector>
#include <queue>
#include "grader.h"
#define endl '\n'
#define ll long long

using namespace std;
int n;
int used[1024];
vector <int> v[1024];
vector <int> mno;
void dfs(int beg)
{
    used[beg]=1;
    mno.push_back(beg);
    ///cout << "-------------" << endl;
    ///cout<<beg<<endl;
    for(int i=0;i<v[beg].size();i++)
    {
        int nb=v[beg][i];
        ///cout << nb << endl;
        if(!used[nb])
        {
            dfs(nb);
        }
    }
}
int bin()
{
    int l=1;
    int r=n,mid;
    while(l<r)
    {
        vector<int> x;
        mid=(l+r)/2;
        for(int i=0;i<mid;i++)
        {
            x.push_back(mno[i]);
        }
        if(query(x))
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    return l-1;
}
int findEgg (int N, vector < pair < int, int > > b)
{
    mno.clear();
    for(int i=1;i<=514;i++)
    {
        v[i].clear();
        used[i]=0;
    }
    n=N;
    for(int i=0;i<b.size();i++)
    {
        v[b[i].first].push_back(b[i].second);
        v[b[i].second].push_back(b[i].first);
    }
    dfs(1);
    //cout<<155555<<endl;
    return mno[bin()];
}

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