Submission #1194343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194343		a0ms1n	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	500 KiB

eastereggs

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

using namespace std;

vector<vector<int>> adjL;
vector<int> path;

void dfs(int u,int p=-1){
    path.push_back(u);
    for(int v:adjL[u]){
        if(v==p)continue;
        dfs(v,u);
    }
}

bool cando(int x){
    vector<int> ans;
    for(int i=0;i<=x;i++)ans.push_back(path[i]);
    return query(ans);
}

int findEgg (int N, vector < pair < int, int > > bridges){
    path.clear();
    adjL.clear();
    adjL.resize(N+1);
    //cout<<"HEY\n";
    for(const auto &[u,v]:bridges){
        adjL[u].push_back(v);
        adjL[v].push_back(u);
    }
    dfs(1);
    int l=0,r = path.size()-1;
    while(l<r){
        int mid = (l+r)/2;
        if(cando(mid))r=mid;
        else l=mid+1;
    }
    return path[r];
}

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