제출 #1220241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220241		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	524 KiB

eastereggs

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

int query(vector<int> nodes); // provided by grader

vector<vector<int>> g;
vector<bool> vis;

void collect(int u, vector<int>& comp) {
    vis[u] = true;
    comp.push_back(u);
    for (int v : g[u]) {
        if (!vis[v]) collect(v, comp);
    }
}

vector<int> get_connected_subset(const vector<int>& from, int need) {
    unordered_set<int> in(from.begin(), from.end());
    vis.assign(g.size(), true); // block everything
    for (int x : from) vis[x] = false;

    vector<int> result;
    for (int u : from) {
        if (!vis[u]) {
            vector<int> tmp;
            collect(u, tmp);
            for (int x : tmp) result.push_back(x);
            if ((int)result.size() >= need) {
                result.resize(need);
                return result;
            }
        }
    }
    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 half = remaining.size() / 2;

        vector<int> part = get_connected_subset(remaining, half);

        if (query(part)) {
            remaining = part;
        } else {
            // use rest = remaining - part
            unordered_set<int> in_part(part.begin(), part.end());
            vector<int> rest;
            for (int x : remaining) {
                if (!in_part.count(x)) rest.push_back(x);
            }

            // Ensure rest is connected: attach it to part if needed
            vector<int> new_query = get_connected_subset(rest, min((int)rest.size(), half));
            for (int x : part) new_query.push_back(x); // attach to ensure connected

            if (query(new_query)) {
                remaining.clear();
                unordered_set<int> in_new(new_query.begin(), new_query.end());
                for (int x : rest) {
                    if (in_new.count(x)) remaining.push_back(x);
                }
            } else {
                // Egg is not in rest → stay in part
                remaining = part;
            }
        }
    }

    return remaining[0];
}

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