Submission #1220236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220236		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	26.40 / 100	7 ms	524 KiB

eastereggs

#include <bits/stdc++.h>
using namespace std;

int query(vector<int> nodes); // Provided externally

vector<vector<int>> g;
vector<bool> visited;
vector<int> subtree;

void collect(int u) {
    visited[u] = true;
    subtree.push_back(u);
    for (int v : g[u]) {
        if (!visited[v]) {
            collect(v);
        }
    }
}

int findEgg(int n, vector<pair<int, int>> edges) {
    g.assign(n + 1, {});
    for (auto [u, v] : edges) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> current;

    // Step 1: Start with a full traversal from node 1
    visited.assign(n + 1, false);
    subtree.clear();
    collect(1);
    current = subtree;

    while (current.size() > 1) {
        // Step 2: Try to extract a connected half from current
        visited.assign(n + 1, false);
        vector<int> half;
        queue<int> q;

        // Start from any node in current
        q.push(current[0]);
        visited[current[0]] = true;
        unordered_set<int> currentSet(current.begin(), current.end());
        half.push_back(current[0]);

        while (!q.empty() && half.size() < current.size() / 2) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (!visited[v] && currentSet.count(v)) {
                    visited[v] = true;
                    q.push(v);
                    half.push_back(v);
                    if (half.size() >= current.size() / 2) break;
                }
            }
        }

        // Step 3: Query the half
        if (query(half)) {
            current = half;
        } else {
            unordered_set<int> halfSet(half.begin(), half.end());
            vector<int> other;
            for (int x : current) {
                if (!halfSet.count(x)) other.push_back(x);
            }
            current = other;
        }
    }

    return current[0];
}

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