Submission #1189857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189857		fluke	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	11 ms	1052 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#define emb emplace_back
#define em emplace

using namespace std;


void dfs(int node , vector <int> &temp , vector <vector <int>> &ask , vector <bool> &vis , vector <vector <int>> &adj){
    temp.emb(node);
    ask[temp.size()] = temp;
    
    for(int next_node : adj[node]){
        if(vis[next_node])continue;
        vis[next_node] = true;
        dfs(next_node,temp,ask,vis,adj);
    }
}


int findEgg (int N, vector < pair < int, int > > bridges)
{
    vector <vector <int>> adj(513);
    vector <vector <int> > ask(513);
    vector <int> temp;
    vector <bool> vis(513);

    for(auto [u,v] : bridges){
        adj[u].emb(v);
        adj[v].emb(u);
    }

    vis[1] = true;
    dfs(1,temp,ask,vis,adj);

    // for(int i=1;i<=N;i++){
    //     cout<<i<<" : " ;
    //     for(auto x : ask[i]){
    //         cout<<x<<" ";
    //     }
    //     cout<<"\n";
    // }

    int left = 1 , right = N;

    int ans = 1;
    while(left < right){
        
        int mid = (left+ right)/2;

        if(query(ask[mid])){
            right = mid;
        }
        else left = mid + 1;
    }

    return ask[right].back();
} 

// int main(){
//     int n;
//     cin>>n;

//     vector <pair<int,int> > edge_list;
//     for(int i = 1 ; i<=n -1 ; i++){
//         int x,y;
//         cin>>x>>y;
//         edge_list.emb(x,y);
//     }

//     findEgg(n,edge_list);
// }

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