Submission #1146053

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

eastereggs

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

using namespace std;

vector<int> ts,pmo[1024]; //path, e
int used[1024];
int n;

bool check(int x)
{
    vector<int> p;
    for(int i=0; i<=x; i++)
    {
        p.push_back(ts[i]);
    }
    return query(p);
}

int dnc()
{
    int l=0,r=ts.size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            r=mid;
        }
        else
            l=mid+1;
    }
    return l;
}
void DFS(int beg)
{
    used[beg]=1;
    ts.push_back(beg);
    for(int i=0; i<pmo[beg].size();i++)
    {
        int nb=pmo[beg][i];
        if(!used[nb])DFS(nb);
    }
}
int findEgg (int N, vector < pair < int, int > > b)
{
    n=N;
    for(int i = 0; i < 1024; i++)
        used[i] = 0;
    ts.clear();
    for(int i=0; i<1024; i++)
    {
        pmo[i].clear();
    }
    for(int i=0;i<b.size();i++)
    {
        pmo[b[i].first].push_back(b[i].second);
        pmo[b[i].second].push_back(b[i].first);
       // cout<<b[i].first<<' '<<b[i].second<<endl;
    }
    DFS(1);
    //reverse(ts.begin(), ts.end());
    return ts[dnc()];
}

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