| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1164712 | adaawf | Easter Eggs (info1cup17_eastereggs) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
vector<int> g[555];
int dd[555], f[555][555], da[555], pp[555][555], db[555];
void dfs(int x, int p, int h, int c) {
c += dd[x];
f[h][x] = c;
pp[h][x] = p;
for (int w : g[x]) {
if (w == p) continue;
dfs(w, x, h, c);
}
}
int findEgg(int n, vector<pair<int, int>> e) {
for (int i = 0; i < n - 1; i++) {
g[e[i].first].push_back(e[i].second);
g[e[i].second].push_back(e[i].first);
}
for (int i = 1; i <= n; i++) dd[i] = 1;
int h = n;
while (h != 1) {
for (int i = 1; i <= n; i++) {
dfs(i, -1, i, 0);
da[i] = 0;
}
vector<int> v, vv;
for (int i = 1; i <= n; i++) {
if (dd[i] == 1) {
v.push_back(i);
vv.push_back(i);
da[i] = 1;
break;
}
}
int j = 0;
while (v.size() < (h + 1) / 2) {
int k = v[j];
for (int i = 1; i <= n; i++) {
if (f[k][i] == 2 && da[i] == 0 && dd[i] == 1) {
v.push_back(i);
int l = i;
while (da[l] == 0) {
vv.push_back(l);
da[l] = 1;
l = pp[k][l];
}
}
if (v.size() == (h + 1) / 2) break;
}
j++;
}
for (int i = 1; i <= n; i++) db[i] = 0;
for (int w : v) db[w] = 1;
if (query(vv)) {
for (int i = 1; i <= n; i++) {
dd[i] = db[i];
}
h = v.size();
}
else {
for (int i = 1; i <= n; i++) {
if (dd[i] == 1 && db[i] == 0) {
dd[i] = 1;
}
else dd[i] = 0;
}
h -= v.size();
}
}
for (int i = 1; i <= n; i++) {
if (dd[i] == 1) return i;
}
return -1;
}