Submission #1220250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220250		giorgi123glm	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	516 KiB

eastereggs

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

using namespace std;

int findEgg (int N, vector < pair < int, int > > input)
{
    vector <vector <int> > gr (N + 1);
    for (auto [a, b] : input) {
        gr[b].emplace_back (a);
        gr[a].emplace_back (b);
    }

    int timer = 0;
    vector <int> in (N + 1);
    vector <int> revin (N + 1);

    function <void(int,int)> dfs =
    [&](int p, int par)->void {
        in[p] = ++timer;
        revin[in[p]] = p;

        for (int& e : gr[p])
            if (e != par)
                dfs (e, p);
    };
    dfs (1, -1);

    auto ask = [&](int L, int R) {
        vector <int> toask;
        for (int i = L; i <= R; i++)
            toask.emplace_back (revin[i]);
        return query (toask);
    };

    int L = 1, R = timer - 1;
    int ans = 0;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (ask (1, mid)) {
            R = mid - 1;
            ans = mid;
        } else
            L = mid + 1;
    }

    return (ans == 0 ? revin[timer] : revin[ans]);
}

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