제출 #1306775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306775		kunzaZa183	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	3 ms	488 KiB

eastereggs

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

using namespace std;

int findEgg(int N, vector<pair<int, int>> bridges) {
  vector<vector<int>> adj(N);
  for (auto [a, b] : bridges) {
    a--, b--;
    adj[a].push_back(b), adj[b].push_back(a);
  }

  vector<int> num(N);
  int ct = 0;
  function<void(int, int)> fvii = [&](int cur, int par) {
    num[cur] = ct++;
    for (auto a : adj[cur])
      if (a != par)
        fvii(a, cur);
  };
  fvii(0, 0);

  int l = 0, r = N - 1;
  while (l < r) {
    // return 0;
    // cout << l << " " << r << "\n";
    int mid = (l + r) / 2;
    vector<int> qry;
    for (int i = 0; i < N; i++)
      if (l <= num[i] && num[i] <= mid)
        qry.push_back(i + 1);

    int x = query(qry);
    // cout << x << "\n";
    if (x == 1) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  return find(num.begin(), num.end(), l) - num.begin() + 1;
}

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