제출 #1062197

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062197		pera	Easter Eggs (info1cup17_eastereggs)	C++17	100 / 100	18 ms	532 KiB

eastereggs

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg(int N , vector<pair<int , int>> bridges){
   vector<int> order;
   vector<vector<int>> g(N + 1);
   for(auto [u , v] : bridges){
      g[u].push_back(v);
      g[v].push_back(u);
   }
   function<void(int , int)> dfs = [&](int u , int p){
      order.emplace_back(u);
      for(int x = 0;x < (int)g[u].size();x ++){
         if(g[u][x] != p){
            dfs(g[u][x] , u);
         }
      }
   };
   dfs(1 , -1);
   auto Query = [&](int x){
      vector<int> u;
      for(int i = 0;i <= x;i ++){
         u.emplace_back(order[i]);
      }
      return query(u);
   };
   int l = 0 , r = N - 1;
   while(l < r){
      int m = (l + r) / 2;
      if(Query(m)){
         r = m;
      }else{
         l = m + 1;
      }
   }
   return order[l];
}

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