Submission #1187381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187381		GGOSHAB	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	676 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;

const int maxn = 512 + 10;

vector<int> g[maxn];
vector<int> order;
void dfs(int v = 1, int p = -1) {
    for (int u : g[v]) {
        if (u != p) {
            dfs(u, v);
        }
    }
    order.push_back(v);
}

int findEgg (int n, vector<pair<int, int>> bridges) {
    for (int v = 1; v <= n; ++v) {
        g[v].clear();
    }

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

    dfs();
    reverse(order.begin(), order.end());
    auto f = [&](int x) {
        vector<int> temp;
        for (int i = 0; i <= x; ++i) {
            temp.push_back(order[i]);
        }
        return query(temp);
    };
    
    int l = -1, r = n - 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (f(m)) {
            r = m;
        } else {
            l = m;
        }
    }

    return order[r];
}

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