Submission #1289961

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289961		oruc	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	2 ms	500 KiB

eastereggs

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

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges)
{
    vector<vector<int>> g(N+1);
    for(int i = 0; i < N-1; i++){
        g[bridges[i].first].push_back(bridges[i].second);
        g[bridges[i].second].push_back(bridges[i].first);
    }
    vector<int> vis(N+1),a;
    function<void(int)> dfs = [&](int v){
        vis[v] = 1;
        a.push_back(v);
        for(int u: g[v]){
            if(!vis[u]){
                dfs(u);
            }
        }
    };

    dfs(1);

    //show(a);

    int l = 0, r = N-1;
    while(l < r){
        int mid = (l+r)/2;
        vector<int> v;
        for(int i = l; i <= mid; i++){
            v.push_back(a[i]);
        }
        int ok = query(v);
        if(ok){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    return a[r];
}

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