제출 #1220249

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

eastereggs

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

int query(vector<int> nodes); // external

vector<vector<int>> g;
vector<bool> removed;

int compute_subtree_sizes(int u, int p, vector<int>& sz, const vector<int>& available) {
    sz[u] = 1;
    for (int v : g[u]) {
        if (v != p && !removed[v] && binary_search(available.begin(), available.end(), v)) {
            sz[u] += compute_subtree_sizes(v, u, sz, available);
        }
    }
    return sz[u];
}

void collect_nodes(int u, int p, vector<int>& nodes) {
    nodes.push_back(u);
    for (int v : g[u]) {
        if (v != p && !removed[v]) {
            collect_nodes(v, u, nodes);
        }
    }
}

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

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

    vector<int> available(n);
    iota(available.begin(), available.end(), 1);
    sort(available.begin(), available.end()); // for binary_search in subtree size calculation

    while (available.size() > 1) {
        int root = available[0];
        vector<int> sz(n + 1, 0);
        compute_subtree_sizes(root, 0, sz, available);

        int total_size = sz[root];
        int found = -1;

        for (int v : g[root]) {
            if (removed[v]) continue;
            if (!binary_search(available.begin(), available.end(), v)) continue;

            vector<int> sub;
            collect_nodes(v, root, sub);

            if ((int)sub.size() * 2 >= total_size) { // roughly half or more
                if (query(sub)) {
                    removed[root] = true;
                    available = sub;
                } else {
                    for (int x : sub) removed[x] = true;
                    vector<int> new_available;
                    for (int x : available) {
                        if (!removed[x]) new_available.push_back(x);
                    }
                    available = new_available;
                }
                found = 1;
                break;
            }
        }

        if (found == -1) {
            // no child was large enough, query the rest (root itself)
            if (query({root})) {
                return root;
            } else {
                removed[root] = true;
                vector<int> new_available;
                for (int x : available) {
                    if (!removed[x]) new_available.push_back(x);
                }
                available = new_available;
            }
        }
    }

    return available[0];
}

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