Submission #1220235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220235		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	3 ms	504 KiB

eastereggs

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

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

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

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

int findEgg(int n, vector<pair<int, int>> edges) {
    g.assign(n + 1, {});
    used.assign(n + 1, false);

    for (auto [u, v] : edges) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> curr;
    curr.push_back(1);

    // Expand to full connected component
    used.assign(n + 1, false);
    subtree.clear();
    collect(1, -1);

    curr = subtree;

    while (curr.size() > 1) {
        // Try to extract a connected component of roughly half the size
        vector<bool> mark(n + 1, false);
        for (int x : curr) mark[x] = true;

        used.assign(n + 1, false);
        vector<int> half;

        for (int u : curr) {
            if (!used[u]) {
                subtree.clear();
                collect(u, -1);
                if (subtree.size() <= curr.size() / 2) {
                    for (int x : subtree) half.push_back(x);
                    if (half.size() >= curr.size() / 2) break;
                }
            }
        }

        // if half not big enough, add nodes from current to make it big and connected
        if (half.size() < curr.size() / 2) {
            for (int x : curr) {
                if (find(half.begin(), half.end(), x) == half.end()) {
                    half.push_back(x);
                    if (half.size() >= curr.size() / 2) break;
                }
            }
        }

        if (query(half)) {
            curr = half;
        } else {
            vector<int> other;
            for (int x : curr) {
                if (find(half.begin(), half.end(), x) == half.end()) {
                    other.push_back(x);
                }
            }
            curr = other;
        }
    }

    return curr[0];
}

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