Submission #1164733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164733		nathan4690	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	536 KiB

eastereggs

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000;

void dfs(int u, int p, int &timer, vector<int> &sp, const vector<vector<int>> &G){
    sp[u] = timer++;
    for(int c: G[u]){
        if(c != p){
            dfs(c, u, timer, sp, G);
        }
    }
}

int findEgg(int N, vector<pair<int,int>> bridges){
    vector<vector<int>> G(N+1);
    for(pair<int,int> e: bridges){
        int u = e.first, v = e.second;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> sp(N + 1);
    int timer = 1;
    dfs(1, 0, timer, sp, G);
    vector<int> perm(N);
    iota(perm.begin(), perm.end(), 1);
    sort(perm.begin(), perm.end(), [&](int u, int v){
         return sp[u] < sp[v];
    });
//    for(int item: perm) cout << item << '\n';
    int L = 0, R = N - 1;
    while(L < R){
        int mid = (L + R) / 2;
        vector<int> ques(perm.begin(), perm.begin() + mid + 1);
        if(query(ques)) R = mid;
        else L = mid + 1;
    }
    return perm[L];
}

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