| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 403578 | hltk | Easter Eggs (info1cup17_eastereggs) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
// int query(vector<int> islands) {
// cout << "query({";
// bool f = 1;
// for (int u : islands) {
// if (!f) cout << ", ";
// f = 0;
// cout << u;
// }
// cout << "}): ";
// int x;
// cin >> x;
// return x;
// }
int findEgg(int n, vector<pair<int, int>> bridges) {
vector<vector<int>> g(n + 1);
for (auto [a, b] : bridges) {
g[a].push_back(b);
g[b].push_back(a);
}
set<int> opts;
for (int i = 1; i <= n; ++i) opts.insert(i);
while (opts.size() > 1) {
int bdiff = 1e9, eid = -1;
for (int i = 0; i < (int) bridges.size(); ++i) {
int a = bridges[i].first, b = bridges[i].second;
if (!opts.count(a) || !opts.count(b)) continue;
function<int(int, int)> dfs = [&](int v, int p) {
int r = 1;
for (auto u : g[v]) {
if (minmax(v, u) == minmax(a, b)) continue;
if (!opts.count(u) || u == p) continue;
r += dfs(u, v);
}
return r;
};
int ax = dfs(a, -1);
int bx = dfs(b, -1);
if (int off = abs(ax - bx); off < bdiff) {
bdiff = off;
eid = i;
}
}
int a = bridges[eid].first, b = bridges[eid].second;
function<set<int>(int, int)> dfs = [&](int v, int p) {
set ret{v};
for (auto u : g[v]) {
if (minmax(v, u) == minmax(a, b)) continue;
if (!opts.count(u) || u == p) continue;
ret.merge(dfs(u, v));
}
return ret;
};
auto o = dfs(a, -1);
if (query({o.begin(), o.end()})) {
auto z = opts;
for (auto u : z) {
if (!o.count(u)) {
opts.erase(u);
}
}
} else {
for (auto u : o) {
opts.erase(u);
}
}
}
assert(opts.size() == 1);
return *opts.begin();
}
// int main() {
// int ret = findEgg(5, {{1, 2}, {1, 3}, {2, 4}, {4, 5}});
// cout << "findEgg: " << ret << endl;
// }