Submission #1220251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220251		takoshanava	Easter Eggs (info1cup17_eastereggs)	C++20	Compilation error	0 ms	0 KiB

eastereggs

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

int query(const vector<int>& nodes);

vector<vector<int>> g;
vector<bool> in_remaining;
vector<int> sz;

int dfs_size(int u, int p) {
    sz[u] = 1;
    for (int v : g[u]) {
        if (v != p && in_remaining[v]) {
            sz[u] += dfs_size(v, u);
        }
    }
    return sz[u];
}

int find_centroid(int u, int p, int total) {
    for (int v : g[u]) {
        if (v != p && in_remaining[v] && sz[v] > total / 2) {
            return find_centroid(v, u, total);
        }
    }
    return u;
}

void collect_nodes(int u, int p, vector<int>& comp) {
    comp.push_back(u);
    for (int v : g[u]) {
        if (v != p && in_remaining[v]) {
            collect_nodes(v, u, 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);
    }

    in_remaining.assign(n + 1, true);
    sz.assign(n + 1, 0);

    int remaining_count = n;

    while (remaining_count > 1) {
        int start = -1;
        for (int i = 1; i <= n; i++) {
            if (in_remaining[i]) {
                start = i;
                break;
            }
        }
        if (start == -1) break; 

        int total = dfs_size(start, 0);
        int centroid = find_centroid(start, 0, total);

        vector<int> comp;
        collect_nodes(centroid, 0, comp);

        if ((int)comp.size() == 1) {
            return comp[0];
        }


        vector<vector<int>> parts;
        vector<bool> visited(n + 1, false);
        visited[centroid] = true;

        for (int v : g[centroid]) {
            if (in_remaining[v] && !visited[v]) {
                vector<int> part;
                function<void(int,int)> dfs_part = [&](int u,int p) {
                    part.push_back(u);
                    visited[u] = true;
                    for (int w : g[u]) {
                        if (w != p && in_remaining[w] && !visited[w]) {
                            dfs_part(w,u);
                        }
                    }
                };
                dfs_part(v, centroid);
                parts.push_back(move(part));
            }
        }

        bool found_part = false;
        for (auto& part : parts) {
            vector<int> query_set = part;
            query_set.push_back(centroid);
            if (query(query_set)) {
                unordered_set<int> keep(query_set.begin(), query_set.end());
                for (int i = 1; i <= n; i++) {
                    if (in_remaining[i] && !keep.count(i)) {
                        in_remaining[i] = false;
                        remaining_count--;
                    }
                }
                found_part = true;
                break;
            }
        }

        if (!found_part) {
            return centroid;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (in_remaining[i]) return i;
    }

    return -1; 
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cctaCEn1.o: in function `findEgg(int, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >)':
eastereggs.cpp:(.text+0xc39): undefined reference to `query(std::vector<int, std::allocator<int> > const&)'
collect2: error: ld returned 1 exit status