Submission #1168805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168805		ChottuF	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 100	8 ms	508 KiB

eastereggs

#include "grader.h"

#include <bits/stdc++.h>

using namespace std;

vector<int> graph[513];
vector<int> all;

void dfs(int x, int p){
    all.push_back(x);
    for (auto u : graph[x]){
        if (u == p) continue;
        else dfs(u,x);
    }
}

int findEgg(int N, vector < pair < int, int > > bridges){
    for (int i = 1; i<=N; i++){
        graph[i].clear();
    }
    all.clear();
    
    for (auto u : bridges){
        graph[u.first].push_back(u.second);
        graph[u.second].push_back(u.first);
    }
    dfs(1,0);
    int lo  = 0;
    int hi = N-1;
    int mid;
    int ans = hi;
    while (lo <= hi){
        mid = (lo+hi)/2;
        if (query(vector<int>(all.begin(),all.begin()+mid+1))){
            //it works
            ans = min(ans, mid);
            hi = mid - 1;
        }
        else{
            lo = mid + 1;
        }
    }
    return all[ans];
}

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