Submission #1145919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145919		tolga	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	456 KiB

eastereggs

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

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

int query(vector<int> islands);

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

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

  vector<int> curr = in;
  while (l <= r) {
    mid = (l + r) / 2;
    if (check(mid)) {
      r = mid;
    } else
      l = mid + 1;
  }
  return mid;
}

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

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);

  return bin_search();
}

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