Submission #983647

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

eastereggs

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

using namespace std;

typedef long long ll;

vector<int> g[1010], 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 (auto &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;
    while (l <= r) {
        int m = (l + r) / 2;
        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