제출 #1138621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138621		fryingduc	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	508 KiB

eastereggs

#include "bits/stdc++.h"
using namespace std;
#include "grader.h"

#ifdef duc_debug
#include "bits/debug.h"
#endif

const int maxn = 550;
int n;
vector<int> g[maxn];
int timer, tin[maxn], et[maxn];

void pre_dfs(int u, int prev) {
  tin[u] = ++timer;
  et[timer] = u;
  for(auto v:g[u]) {
    if(v == prev) continue;
    pre_dfs(v, u);
  }
}

int findEgg(int n, vector<pair<int, int>> edges) {
  for(int i = 1; i <= n; ++i) {
    g[i].clear();
  }
  for(auto i:edges) {
    int u = i.first, v = i.second;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  timer = 0;  
  pre_dfs(1, 0);
  int l = 1, r = n - 1, res = -1;
  while(l <= r) {
    int mid = (l + r) >> 1;
    vector<int> v;
    for(int i = 1; i <= mid; ++i) {
      v.push_back(et[i]);
    }
    if(query(v)) {
      res = mid;
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  if(res == -1) res = n;
  return et[res];
}

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