Submission #1066196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066196		Malix	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	18 ms	600 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

int findEgg (int N, vector < pair < int, int > > bridges)
{
    int n=N;
    vii a(n);
    REP(i,0,n-1){
        a[bridges[i].F-1].PB(bridges[i].S-1);
        a[bridges[i].S-1].PB(bridges[i].F-1);
    }
    vi vis(n,0);
    vi arr;
    queue<int> pq;
    pq.push(0);
    while(!pq.empty()){
        int x=pq.front();
        pq.pop();
        if(vis[x])continue;
        vis[x]=1;
        arr.PB(x);
        for(auto u:a[x])pq.push(u);
    }
    int l=0,r=n-1;
    while(l<r){
        int m=(l+r)/2;
        vi b;
        REP(i,0,m+1)b.PB(arr[i]+1);
        if(!query(b))l=m+1;
        else r=m;
    }
    return arr[l]+1;
}

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