Submission #1192843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192843		gml	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	524 KiB

eastereggs

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

using namespace std;

int findEgg(int N, vector<pair<int, int>> bridges) {
    int n = N;
    vector<vector<int>> tree(n);
    vector<int> lb(n), ub(n);

    function<void(int,int,int&)> Euler_tour = [&](int u, int pred, int & id) {
        lb[u] = id++;
        for (int v : tree[u])
            if (v != pred)
                Euler_tour(v, u, id);
        ub[u] = id - 1;
    };

    for(auto [u, v] : bridges) {
        u--, v--;  // assuming input is 1-based
        tree[u].push_back(v);
        tree[v].push_back(u);
    }

    int root = 0, id = 0;
    Euler_tour(root, -1, id);

    vector<int> v(n);
    for (int i = 0; i < n; i++) v[lb[i]] = i + 1;

    int l = 0, r = n - 1;
    while (l < r) {
        int m = (r - l) / 2;
        int up = (l + m + 1);

        vector<int> ask;
        for (int i = 0; i < up; i++) {
            ask.push_back(v[i]);
        }

        bool b = query(ask);  // call the function that answers

        if (b)
            r = up - 1;
        else
            l = up;
    }

    return v[l];
}

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