Submission #1242846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242846		rhm_gan	Easter Eggs (info1cup17_eastereggs)	C++20	10 / 100	1 ms	504 KiB

eastereggs

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

int n;
vector<int> sz;
vector<vector<int>> g;

void dfs_sz(int u, int p) {
    sz[u] = 1;
    for (auto v : g[u]) {
        if (v != p) {
            dfs_sz(v, u);
            sz[u] += sz[v];
        }
    }
}

int centroid(int u, int p) {
    for (auto v : g[u]) {
        if (v != p && sz[v] * 2 > n) {
            return centroid(v, u);
        }
    }
    return u;
}

vector<int> sub;
void subtree(int u, int p) {
    sub.push_back(u);
    for (auto v : g[u]) {
        if (v != p) {
            subtree(v, u);
        }
    }
}

int dfs(int u, int p) {
    for (auto v : g[u]) {
        if (v == p) continue;
        subtree(v, u);
        if (sub.empty()) {
            return v;
        }
        int res = query(sub);
        sub.clear();
        if (res) {
            return dfs(v, u);
        }
    }
    return u;
}

int findEgg (int N, vector<pair<int, int>> bridges) {
    n = N;
    g.assign(n + 1, vector<int>());
    sz.assign(n + 1, 0);
    for (auto [u, v] : bridges) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_sz(1, 0);
    int c = centroid(1, 0);

    return dfs(centroid(1, 0), 0);
}

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