Submission #1308439

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

eastereggs

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

using namespace std;

const int MAXN = 1005; 
vector<int> adj[MAXN];
vector<int> order;

void buildOrder(int n) {
    order.clear();
    vector<bool> visited(n + 1, false);
    queue<int> q;

    q.push(1);
    visited[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);

        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int findEgg(int N, vector<pair<int, int>> bridges) {
    for (int i = 1; i <= N; i++) adj[i].clear();
    
    for (auto &edge : bridges) {
        adj[edge.first].push_back(edge.second);
        adj[edge.second].push_back(edge.first);
    }

    buildOrder(N);

    int low = 0, high = N - 2; 
    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: 40 / 40
• Subtask 2: 40 / 40
• Subtask 3: 20 / 20