Submission #1224745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224745		bynix	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	508 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
#define a(k) begin(k), begin(k)

void dfs(int c, int par, vector<int>& p, vector<vector<int>>& adj){
  p.push_back(c);
  for (auto &e: adj[c])
    if (e != par) dfs(e, c, p, adj);
}

int findEgg (int N, vector<pair<int, int>> bridges){
  vector<vector<int>> adj(N+1);
  for (auto &e: bridges){
    adj[e.first].push_back(e.second);
    adj[e.second].push_back(e.first);
  }

  vector<int> p;
  dfs(1, 0, p, adj);

  int l = 0, r = N-1;
  while (l < r){
    int mid = l + (r-l+1)/2;
    if (query(vector<int>(a(p) + mid))) r = mid - 1;
    else l = mid;
  }
  return p[l];
}

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