제출 #1139262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139262		JelalTkm	Easter Eggs (info1cup17_eastereggs)	C++20	87 / 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 = 0, r = n + 1;
  while (r - l > 1) {
    int mid = (l + r) >> 1;
    vector<int> qu;
    for (int i = 1; i < mid; i++)
      qu.push_back(w[i]);
    if (!qu.empty() && query(qu))
      r = mid;
    else l = mid;
  }
  
  return w[r - 1];
}

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