제출 #1145938

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

eastereggs

#include "grader.h"
#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, curr;
bool visited[maxv];

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

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;
  }
  return 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: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20