Submission #1220248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220248		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	488 KiB

eastereggs

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

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

vector<vector<int>> g;

vector<int> get_connected(const vector<int>& from, int want) {
    unordered_set<int> in(from.begin(), from.end());
    vector<bool> vis(g.size(), false);
    vector<int> result;
    queue<int> q;

    for (int x : from) {
        q.push(x);
        vis[x] = true;
        break;
    }

    while (!q.empty() && (int)result.size() < want) {
        int u = q.front(); q.pop();
        if (!in.count(u)) continue;
        result.push_back(u);
        for (int v : g[u]) {
            if (!vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }

    return result;
}

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> remaining(n);
    iota(remaining.begin(), remaining.end(), 1);

    while ((int)remaining.size() > 1) {
        int sz = remaining.size();
        int half = sz / 2;

        vector<int> a = get_connected(remaining, half);
        unordered_set<int> in_a(a.begin(), a.end());

        if (query(a)) {
            remaining = a;
        } else {
            vector<int> b;
            for (int x : remaining)
                if (!in_a.count(x)) b.push_back(x);

            vector<int> comp_b = get_connected(b, half);
            vector<int> query_set = comp_b;

            for (int i = 0; i < (int)a.size() && query_set.size() < half * 2; ++i)
                query_set.push_back(a[i]); // attach to ensure connectedness

            if (query(query_set)) {
                unordered_set<int> in_comp_b(comp_b.begin(), comp_b.end());
                vector<int> next;
                for (int x : query_set)
                    if (in_comp_b.count(x)) next.push_back(x);
                remaining = next;
            } else {
                remaining = a;
            }
        }
    }

    return remaining[0];
}

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