Submission #487927

#	Time	Username	Problem	Language	Result	Execution time	Memory
487927		Drew_	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	15 ms	356 KiB

eastereggs

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

using namespace std;

#define pb push_back

constexpr int MAX = 569;

bool dead[MAX] = {};
vector<int> adj[MAX], order;

void dfs(int node, int par)
{
    order.pb(node);
    for (int to : adj[node])
        if (to != par)
            dfs(to, node);
}

int findEgg (int N, vector < pair < int, int > > bridges)
{
    order.clear();
    for (int i = 1; i <= N; ++i)
        adj[i].clear(), dead[i] = false;

    for (auto &[u, v] : bridges)
        adj[u].pb(v), adj[v].pb(u);
    dfs(1, -1);

    while (N > 1)
    {
        int mid = N >> 1;

        int ctr = 0;
        vector<int> v;
        for (int x : order)
        {
            ctr += !dead[x];
            v.pb(x);
            
            if (ctr == mid)
                break;
        }

        if (query(v))
        {
            bool ok = false;
            for (int x : order)
            {
                if (ok)
                    dead[x] = true;

                if (x == v.back())
                    ok = true;
            }

            N = mid;
        }
        else
        {
            for (int x : v)
                dead[x] = true;
            N -= mid;
        }
    }

    for (int x : order)
        if (!dead[x])
            return x;

    return -1;
}

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