제출 #575416

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575416		spensa	Easter Eggs (info1cup17_eastereggs)	C++14	80 / 100	16 ms	464 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define pb push_back

vector<int> G[512];
vector<int> arr;

void dfs(int a, int b){
    // cout<<"a="<<a<<" ";
    arr.pb(a);
    for(auto k: G[a]){
        if(k==b) continue;
        dfs(k,a);
    }
}

int findEgg(int N, vector<pair<int,int>> bridges){
    for(int i=1; i<=N; i++) G[i].clear();
    arr.clear();

    for(auto k:bridges){
        G[k.first].pb(k.second);
        G[k.second].pb(k.first);
    }

    dfs(1, 0);

    // for(int i=0; i<N; i++){
    //     cout<<arr[i]<<" ";
    // }

    int l=0, r=N-1, mid;
    while(l!=r){
        mid = (l + r +1)/2;
        // cout<<mid<<" ";
        if(query(vector<int>(arr.begin(), arr.begin()+mid))){
            r = mid-1;
        }
        else l = mid;
    }

    return arr[l];
}

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