Submission #1321686

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

eastereggs

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

//int query(vector<int> islands);

static const int MAXN = 520;
vector<int> adj[MAXN];
bool removed[MAXN];
int subSize[MAXN];
int N;

// Computer sub-tree sizes
void dfsSize(int u, int p) {
    subSize[u] = 1;
    for (int v : adj[u]) {
        if (v == p || removed[v]) continue;
        dfsSize(v, u);
        subSize[u] += subSize[v];
    }
}

// Find Centroid
int dfsCentroid(int u, int p, int total) {
    for (int v : adj[u]) {
        if (v == p || removed[v]) continue;
        if (subSize[v] > total / 2)
            return dfsCentroid(v, u, total);
    }
    return u;
}

int getCentroid(int root) {
    dfsSize(root, -1);
    return dfsCentroid(root, -1, subSize[root]);
}

// Collect all nodes in a component
void collect(int u, int p, vector<int>& comp) {
    comp.push_back(u);
    for (int v : adj[u]) {
        if (v == p || removed[v]) continue;
        collect(v, u, comp);
    }
}

// Recursive solve function
int solve(int root) {
    int c = getCentroid(root);

    // If there is only 1 node left
    dfsSize(c, -1);
    if (subSize[c] == 1)
        return c;

    removed[c] = true;

    for (int v : adj[c]) {
        if (removed[v]) continue;

        vector<int> component;
        collect(v, c, component);

        // Make query set: centroid + component
        vector<int> ask = component;
        ask.push_back(c);

        if (query(ask)) {
            return solve(v);
        }
    }

    // If egg is not in any component, it must be the centroid
    return c;
}

int findEgg(int n, vector<pair<int,int>> bridges) {
    N = n;

    for (int i = 1; i <= N; i++) {
        adj[i].clear();
        removed[i] = false;
    }

    for (auto &e : bridges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    return solve(1);
}

Compilation message (stderr)

eastereggs.cpp: In function 'int solve(int)':
eastereggs.cpp:67:13: error: 'query' was not declared in this scope
   67 |         if (query(ask)) {
      |             ^~~~~