Submission #1306781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306781		kunzaZa183	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	10 ms	512 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> dep(N);
  function<void(int, int, int)> fvii = [&](int cur, int par, int dpi) {
    dep[cur] = dpi;
    for (auto a : adj[cur])
      if (a != par)
        fvii(a, cur, dpi + 1);
  };
  fvii(0, 0, 0);

  vector<int> all(N);
  iota(all.begin(), all.end(), 0);
  sort(all.begin(), all.end(), [&](int a, int b) { return dep[a] < dep[b]; });

  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 <= mid; i++) {
      qry.push_back(all[i] + 1);
    }

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

  return all[l] + 1;
}

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