Submission #1145967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145967		tolga	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	508 KiB

eastereggs

#include "grader.h"
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
#define endl '\n'

const int maxv = 1e3;
vector<int> edges[maxv];
vector<int> in;
bool visited[maxv];

bool check(int mid) {
  vector<int> p;
  for (int i = 0; i <= mid; i++)
    p.push_back(in[i]);
  return query(p);
}

void dfs(int start) {
  in.push_back(start);
  visited[start] = true;
  for (int next : edges[start])
    if (!visited[next])
      dfs(next);
}

int bin_search() {
  dfs(1);

  int l = 0, r = in.size() - 1;
  int mid;

  while (l < r) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }

  return in[r];
}

void clear() {
  for (int i = 0; i < maxv; i++)
    edges[i].clear();
  memset(visited, false, sizeof(visited));
  in = {};
}

int findEgg(int n, vector<pair<int, int>> bridges) {
  clear();
  for (auto &[u, v] : bridges) {
    edges[u].push_back(v);
    edges[v].push_back(u);
  }

  return bin_search();
}

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