Submission #1139243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139243		JelalTkm	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	1 ms	460 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

using namespace std;

// #define int long long int

// const int N = 1e5 + 100;
// const int md = 1e9 + 7;
// const int INF = 1e9;

int findEgg(int n, vector<pair<int, int>> bri) {
  vector<vector<int>> g(n + 1, vector<int> ());
  for (int i = 0; i < n - 1; i++) {
    auto [u, v] = bri[i];
    g[u].push_back(v);
    g[v].push_back(u);
  }

  queue<int> q;
  vector<bool> visited(n + 1);
  q.push(1);
  visited[1] = 1;
  vector<int> w;
  while (!q.empty()) {
    auto u = q.front();
    w.push_back(u);
    q.pop();
    for (auto v : g[u])
      if (!visited[v]) {
        q.push(v);
        visited[v] = 1;
      }
  }

  int l = -1, r = n;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    vector<int> qu;
    for (int i = l + 1; i < mid; i++)
      qu.push_back(w[i]);
    if (qu.empty()) {
      l = mid;
      continue;
    }
    bool ok = query(qu);
    if (ok)
      r = mid;
    else l = mid;
  }

  return w[r];
}

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