Submission #1220238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220238		lukasuliashvili	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	5 ms	464 KiB

eastereggs

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

int query(vector<int> nodes); // Provided externally

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

void dfs_size(int u, int p) {
    sizes[u] = 1;
    for (int v : g[u]) {
        if (v != p && !removed[v]) {
            dfs_size(v, u);
            sizes[u] += sizes[v];
        }
    }
}

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

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

int decompose(int root) {
    dfs_size(root, -1);
    int total = sizes[root];
    int centroid = find_centroid(root, -1, total);

    removed[centroid] = true;

    for (int v : g[centroid]) {
        if (!removed[v]) {
            vector<int> subtree;
            collect_subtree(v, centroid, subtree);

            if (query(subtree)) {
                return decompose(v);
            }
        }
    }

    return centroid;
}

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

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

    return decompose(1);
}

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