#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges){
vector<int> used(1 + N, 0);
int LEN = N;
for (int i = 1; i <= N; i++)
used[i] = 1;
while ((int)count(used.begin() + 1, used.end(), 1) > 0) {
int oldC = count(used.begin() + 1, used.end(), 1);
vector<vector<int>> g(1 + N);
for (auto it : bridges) {
int a, b;
tie(a, b) = it;
if (!used[a] || !used[b]) continue;
g[a].push_back(b);
g[b].push_back(a);
}
if (LEN <= 2) {
for (auto i = 1; i <= N; i++) {
if (used[i])
if (query({i}))
return i;
}
//assert(false);
}
vector<int> heavy(1 + N, -1), comp;
function<int(int, int)> dfs = [&](int v, int p) {
int size = 1, mx_size = 0;
for (auto to : g[v]) {
if (to == p) continue;
int c_size = dfs(to, v);
size += c_size;
if (c_size > mx_size) {
mx_size = c_size;
heavy[v] = to;
}
}
return size;
};
function<void(int, int)> decompose = [&](int v, int p) {
comp.push_back(v);
if (heavy[v] != -1)
decompose(heavy[v], v);
for (auto to : g[v]) {
if (to == p || to == heavy[v]) continue;
decompose(to, v);
}
};
deque<vector<int>> v;
function<int(vector<int>)> check = [&](vector<int> comp) {
vector<int> p(1 + N), s(1 + N), incomp(1 + N, 0);
for (int i = 1; i <= N; i++) p[i] = i, s[i] = 1;
function<int(int)> get = [&](int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
};
for (auto it : comp) incomp[it] = 1;
for (auto it : bridges) {
int a, b;
tie(a, b) = it;
if (!used[a] || !used[b]) continue;
if (incomp[a] || incomp[b]) continue;
if (get(a) != get(b)) {
if (s[a] < s[b]) swap(a, b);
s[a] += s[b];
p[b] = a;
}
}
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (used[i] && !incomp[i]) cnt++;
}
return (cnt == s[get(1)] ? 1 : 0);
};
for (int s = 1; s <= N; s++) {
if (!used[s]) continue;
heavy.assign(1 + N, -1);
comp.clear();
dfs(s, -1);
decompose(s, -1);
if (check(comp)) {
v.push_front(comp);
} else {
v.push_back(comp);
}
}
if (v.empty()) assert(false);
vector<int> Q;
for (int i = 0; i < max(1, min((LEN+1)/2, (int)v[0].size())); i++)
Q.push_back(v[0][i]);
if (1 == query(Q)) {
if (Q.size() == 1)
return Q[0];
vector<int> incomp(1 + N, 0);
for (auto it : Q) incomp[it] = 1;
for (int i = 1; i <= N; i++) {
if (incomp[i] == 0 && used[i] == 1)
used[i] = 0,
LEN--;
}
} else {
for (auto it : Q)
used[it] = 0;
LEN -= Q.size();
}
int C = count(used.begin() + 1, used.end(), 1);
if (C == oldC) assert(false);
}
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
200 KB |
Number of queries: 5 |
| 2 |
Partially correct |
2 ms |
200 KB |
Number of queries: 6 |
| 3 |
Partially correct |
3 ms |
200 KB |
Number of queries: 7 |
| 4 |
Partially correct |
3 ms |
200 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
111 ms |
620 KB |
Number of queries: 10 |
| 2 |
Partially correct |
335 ms |
968 KB |
Number of queries: 29 |
| 3 |
Execution timed out |
1025 ms |
1340 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
996 ms |
1568 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
