Submission #983650

#	Time	Username	Problem	Language	Result	Execution time	Memory
983650		voidpoint11	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	14 ms	3752 KiB

eastereggs

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

using namespace std;

typedef long long ll;

const int mxN = 1e5;

vector<int> g[mxN], ans;

void dfs(int u, int p) {
    ans.push_back(u);
    for (auto &v : g[u])
        if (v != p)
            dfs(v, u);
}

int findEgg(int n, vector<pair<int, int>> bridges) {
    for (int i = 1; i <= n; i++)    g[i].clear();
    for (pair<int, int> &i : bridges)
        g[i.first].push_back(i.second), g[i.second].push_back(i.first);
    dfs(1, 0);
    int l = 0, r = n - 2, m;
    while (l <= r) {
        m = (l + r) >> 1;
        if (query(vector<int>(ans.begin(), ans.begin() + m + 1)))   r = m - 1;
        else                                                        l = m + 1;
    }
    return ans[l];
}

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