| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 410443 | 2021-05-22T17:09:28 Z | nichke | Easter Eggs (info1cup17_eastereggs) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
using namespace std;
vector< int > vi;
vector< int > euler;
vector< int > adj[513];
bool check(vector <int> );
void dfs(int v, int p = -1) {
euler.push_back(v);
for (int u : adj[v]) {
if (u == p) continue;
dfs(u, p);
}
}
bool check_query(int x) {
vi.clear();
for (int i = 0; i <= x; i++) {
vi.push_back(i);
}
return check(vi);
}
int findEgg(int N, vector< pair <int, int> > bridges) {
euler.clear();
for (int i = 1; i <= N; i++) {
adj[i].clear();
}
for (int i = 0; i < N - 1; i++) {
adj[bridges[i].first].push_back(bridges[i].second);
adj[bridges[i].second].push_back(bridges[i].first);
}
dfs(1);
int res = -1;
int l = 0, r = euler.size() - 1;
while (l <= r) {
int m = (l + r) / 2;
if (check_query(m)) {
r = m - 1;
res = m;
} else {
l = m + 1;
}
}
return euler[res];
}