제출 #1139256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139256		JelalTkm	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	492 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 = 5e2 + 20;
// const int md = 1e9 + 7;
// const int INF = 1e9;

vector<vector<int>> g(N, vector<int> ());
vector<bool> visited(N);
vector<int> w(N);

int findEgg(int n, vector<pair<int, int>> bri) {
  for(int i = 1; i <= n; i++) {
    g[i].clear();
    visited[i] = 0;
  }

  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;
  q.push(1);
  visited[1] = 1;
  int c = 0;
  while (!q.empty()) {
    auto u = q.front();
    w[++c] = u;
    q.pop();
    for (auto v : g[u])
      if (!visited[v]) {
        q.push(v);
        visited[v] = 1;
      }
  }

  int l = 1, r = n - 1, ans = n;
  while(l <= r) {
    int mid = (l + r) >> 1;
    vector<int> v;
    for(int i = 1; i <= mid; i++)
      v.push_back(w[i]);
    if(query(v)) {
      ans = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  
  return w[ans];
}

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