Submission #370600

#	Time	Username	Problem	Language	Result	Execution time	Memory
370600		Sorting	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	24 ms	652 KiB

eastereggs

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

using namespace std;

const int N = 512 + 3;

int n, order[N], t;
vector<int> adj[N];

void dfs(int u, int p = -1){
    order[t++] = u;
    for(int to: adj[u])
        if(to != p)
            dfs(to, u);
}

bool check(int mid){
    vector<int> v;
    for(int i = 0; i <= mid; ++i)
        v.push_back(order[i]);
    return query(v);
}

int findEgg(int _N, vector<pair<int, int>> _bridges){
    n = _N;
    for(int i = 1; i <= n; ++i) adj[i].clear();
    for(auto [x, y]: _bridges){
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    t = 0;
    dfs(1);

    int l = 0, r = n - 1;
    while(l != r){
        int mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return order[l];
}

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