제출 #1166105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166105		irmuun	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	484 KiB

eastereggs

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int findEgg(int n,vector<pair<int,int>>g){
    vector<int>f[n+5];
    for(auto [a,b]:g){
        f[a].pb(b);
        f[b].pb(a);
    }
    queue<int>q;
    q.push(1);
    vector<int>v;
    vector<bool>used(n+5,false);
    used[1]=true;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        v.pb(x);
        for(int y:f[x]){
            if(!used[y]){
                used[y]=true;
                q.push(y);
            }
        }
    }
    int lo=0,hi=n-1;
    while(lo<hi){
        int mid=(lo+hi)/2;
        vector<int>ask;
        for(int i=0;i<=mid;i++){
            ask.pb(v[i]);
        }
        if(query(ask)==1){
            hi=mid;
        }
        else{
            lo=mid+1;
        }
    }
    return v[lo];
}

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