제출 #1358976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1358976		guguguggug	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	6 ms	500 KiB

eastereggs

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

vector<vector<int>> adjL;
int euler[(int)515],dfstime=1;

void dfs(int u,int p=1){
    euler[dfstime++]=u;
    for(int v:adjL[u])if(v!=p)dfs(v,u);
}

bool cando(int x){
    vector<int> g;
    for(int i=1;i<=x;i++)g.push_back(euler[i]);
    return query(g);
}

int findEgg (int N, vector <pair<int,int>> bridges){
    adjL.assign(N+1,vector<int>());
    for(auto &[u,v]:bridges){
        adjL[u].push_back(v);
        adjL[v].push_back(u);
    }
    dfstime = 1;
    dfs(1,1);
    int ans = -1;
    int l=1,r=N-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(cando(mid))ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans == -1)return euler[N];
    return euler[ans];
}

• 서브태스크 1: 40 / 40
• 서브태스크 2: 40 / 40
• 서브태스크 3: 20 / 20