Submission #1129354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129354		matthew	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	11 ms	492 KiB

eastereggs

#include <vector>
#include <utility>
#include "grader.h"

const int MAX_N = 512;

std::vector<int> adj[MAX_N];
int ptr, order[MAX_N];

void clear_adj(int n) {
  for(int i = 0; i < n; i++) {
    adj[i].clear();
  }
}

void dfs(int u, int prev = -1) {
  order[ptr++] = u;
  for(int v : adj[u]) {
    if(v != prev) {
      dfs(v, u);
    }
  }
}

bool found_egg(int pref) {
  std::vector<int> q;
  for(int i = 0; i <= pref; i++) {
    q.push_back(order[i] + 1);
  }
  return query(q);
} 

int findEgg(int n, std::vector<std::pair<int, int>> bridges) {
  clear_adj(n);
  for(std::pair<int, int> x : bridges) {
    adj[x.first - 1].push_back(x.second - 1);
    adj[x.second - 1].push_back(x.first - 1);
  }
  ptr = 0;
  dfs(0);

  int st = -1;
  int dr = n - 1;
  while(dr - st > 1) {
    int mij = (st + dr) / 2;
    if(found_egg(mij)) {
      dr = mij;
    } else {
      st = mij;
    }
  }
  return order[dr] + 1;
}

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