Submission #576501

#	Time	Username	Problem	Language	Result	Execution time	Memory
576501		MEGalodon	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	22 ms	468 KiB

eastereggs

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

using namespace std;

vector<int> adj_lst[MAXN];
vector<int> dfsOrder;
int it = 0;

void dfs(int i, int p){
    if( it ) return;
    dfsOrder.push_back(i);
    for( int j : adj_lst[i] ){
        if( j == p ) continue;
        dfs(j, i);
    }
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
    //for( int i{1} ; i <= N ; ++i ) adj_lst[i].clear();
    for( auto e : bridges ){
        if( it ) break;
        adj_lst[e.first].push_back(e.second);
        adj_lst[e.second].push_back(e.first);
    }
    //dfsOrder.clear();
    dfs(1, 0);
    it = 1;
    int l = 0, r = N-1;
    int m; vector<int> q;
    //for( int x : dfsOrder ) cout<<x<<" "; cout<<'\n';
    while( l < r ){
        m = (l+r)/2;
        q.clear(); q.assign(dfsOrder.begin(), dfsOrder.begin()+m+1);
        if(query(q)) r = m;
        else l = m+1;
    }
    //cout<<l<<'\n';
    return dfsOrder[l];
}

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