Submission #1248351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248351		fve5	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	484 KiB

eastereggs

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

using namespace std;

int findEgg (int N, vector<pair<int, int>> bridges) {
    vector<vector<int>> adj(N);
    for (auto [u, v]: bridges) {
        adj[u - 1].push_back(v - 1);
        adj[v - 1].push_back(u - 1);
    }

    vector<int> order;
    auto dfs = [&](auto &&dfs, int node, int par = -1) -> void {
        order.push_back(node + 1);
        for (auto x: adj[node])
            if (x != par)
                dfs(dfs, x, node);
    };

    dfs(dfs, 0);

    int l = 0, r = N;
    while (r - l > 1) {
        int m = (l + r) / 2;

        bool ans = query(vector<int>(order.begin(), order.begin() + m));

        if (ans) r = m;
        else l = m;
    }

    return order[l];
}

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