oj.uz

Submission #1062197

# Submission time Handle Problem Language Result Execution time Memory
1062197 2024-08-16T21:17:25 Z pera Easter Eggs (info1cup17_eastereggs) C++17
100 / 100
 18 ms 532 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Number of queries: 4
2 Correct 1 ms 344 KB Number of queries: 4
3 Correct 1 ms 344 KB Number of queries: 4
4 Correct 1 ms 344 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Number of queries: 8
2 Correct 9 ms 488 KB Number of queries: 9
3 Correct 11 ms 484 KB Number of queries: 9
4 Correct 9 ms 500 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 532 KB Number of queries: 9
2 Correct 11 ms 492 KB Number of queries: 9
3 Correct 18 ms 344 KB Number of queries: 9
4 Correct 11 ms 500 KB Number of queries: 9