Submission #1308435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308435		mxhrvs	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	8 ms	512 KiB

eastereggs

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

using namespace std;

const int MAXN = (int)1e5+5;
vector<int> adj[MAXN];
vector<int> order;

void buildOrder(int u, int p) {
    order.push_back(u);
    for (int v : adj[u]) {
        if (v != p) {
            buildOrder(v, u);
        }
    }
}

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

    for (auto edge : bridges) {
        adj[edge.first].push_back(edge.second);
        adj[edge.second].push_back(edge.first);
    }

    buildOrder(1, 0);

    int low = 0, high = N - 1;
    int ans = order[N - 1]; 

    while (low <= high) {
        int mid = low + (high - low) / 2;

        vector<int> current_query;
        for (int i = 0; i <= mid; i++) {
            current_query.push_back(order[i]);
        }

        if (query(current_query) == 1) {
            ans = order[mid];
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return ans;
}

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