Submission #1145910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145910		kolio642	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	8 ms	512 KiB

eastereggs

#include <iostream>
#include <vector>
#include "grader.h"
#define endl '\n'

using namespace std;

const int MAXN = 1024;

vector < int > e[MAXN];
vector < int > order;
int n;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

void dfs(int node, int parent)
{
    order.push_back(node);

    for(int &nb : e[node])
    {
        if(nb == parent)
            continue;

        dfs(nb, node);
        //order.push_back(node);
    }
}

bool check(int mid)
{
    vector < int > q;
    q.clear();

    for(int i = 0 ; i <= mid ; i++)
    {
        q.push_back(order[i]);
    }

    /**
    cout << "check --> " << mid <<endl;
    for(int i : q)
        cout << i << ' ';
    cout << endl;

    cout << "query_Ans --> " << query(q) <<endl;
    **/

    int qAns = query(q);
    return qAns;
}

int binarySearch()
{
    int L = 0, R = order.size() - 1, mid;
    while(L < R)
    {
        mid = (L + R) / 2;

        if(check(mid))
            R = mid;
        else
            L = mid + 1;
    }

    return order[L];
}

void read(int N, vector < pair < int, int > > &bridges)
{
    n = N;

    for(pair <int , int>& i : bridges)
    {
        e[i.first].push_back(i.second);
        e[i.second].push_back(i.first);
    }
}

void clearMemory()
{
    for(int i = 0 ; i < MAXN ; i++)
    {
        e[i].clear();
    }
    order.clear();
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    //cout << "--------------" << endl;
    read(N, bridges);

    dfs(1, -1);

    /**
    cout << "Order: ";
    for(int i : order)
        cout << i << ' ';

    cout << endl;
    **/


    int ans = binarySearch();

    clearMemory();

    return ans;
}
/**
13
1 2
1 6
1 5
5 4
3 7
5 3
2 9
2 8
9 11
9 13
10 13
13 12
13
1 2 3 4 5 6 7 8 9 10 11 12 13
**/

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