#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges){
vector<int> par(1 + N);
vector<vector<int>> g(1 + N);
for (auto it : bridges) {
int a, b;
tie(a, b) = it;
g[a].push_back(b);
g[b].push_back(a);
}
set<int> st;
for (int i = 1; i <= N; i++)
st.insert(i);
while (true) {
vector<int> comp;
function<void(int, int)> dfs = [&](int v, int p) {
comp.push_back(v);
for (auto to : g[v]) {
if (to == p) continue;
if (!st.count(to)) continue;
dfs(to, v);
}
};
vector<vector<int>> v;
for (auto it : st) {
while (!comp.empty()) comp.pop_back();
dfs(it, -1);
v.push_back(comp);
}
sort(v.begin(), v.end(), [&](vector<int> a, vector<int> b) {
int cnta = 0, cntb = 0;
for (auto to : g[a[0]]) {
if (st.count(to)) cnta++;
}
for (auto to : g[b[0]]) {
if (st.count(to)) cntb++;
}
if (cnta != cntb) return cnta < cntb;
return a.size() > b.size();
});
vector<int> Q;
for (int i = 0; i < max(1,min((int)v[0].size(), (int)st.size()/2)); i++) {
Q.push_back(v[0][i]);
}
if (query(Q) == 1) {
if (Q.size() == 1) return Q[0];
set<int> h;
for (auto it : Q) h.insert(it);
for (int i = 1; i <= N; i++) if (st.count(i) && !h.count(i)) st.erase(i);
} else {
for (auto it : Q) st.erase(it);
}
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
200 KB |
Number of queries: 5 |
| 2 |
Partially correct |
1 ms |
200 KB |
Number of queries: 7 |
| 3 |
Partially correct |
2 ms |
200 KB |
Number of queries: 9 |
| 4 |
Partially correct |
3 ms |
200 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
612 KB |
Number of queries: 9 |
| 2 |
Execution timed out |
425 ms |
1016 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
854 ms |
1460 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
