Submission #1220245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220245		takoshanava	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);

vector<vector<int>> g;
vector<bool> blocked;

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

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

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

    return comp;
}

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 (remaining.size() > 1) {
        int half = remaining.size() / 2;
        vector<int> a = get_component(remaining, half);

        if (query(a)) {
            remaining = a;
        } else {
            unordered_set<int> in_a(a.begin(), a.end());
            vector<int> rest;
            for (int x : remaining) {
                if (!in_a.count(x)) rest.push_back(x);
            }

            vector<int> b = get_component(rest, half);
            vector<int> b_query = b;

            unordered_set<int> b_set(b.begin(), b.end());
            for (int x : a) {
                if ((int)b_query.size() >= half) break;
                if (!b_set.count(x)) b_query.push_back(x);
            }

            if (query(b_query)) {
                remaining = b;
            } else {
                remaining = a;
            }
        }
    }

    return remaining[0];
}

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