Submission #1220227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220227		giorgi123glm	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	504 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> out (N + 1);
    vector <int> revin (N + 1);

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

        for (int& e : gr[p])
            if (e != par)
                dfs (e, p);
        
        out[p] = timer;
    };
    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;
    while (L < R) {
        int mid = (L + R) / 2;
        if (ask (L, mid) >= 1)
            R = mid;
        else
            L = mid + 1;
    }

    return L;
}

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