#include <bits/stdc++.h>
#include "grader.h"
//#include "grader.cpp"
using namespace std;
#define EMT ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using ull = uint64_t;
using uint = uint32_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const ll LINF = 1e18;
const double EPS = 1e-9;
vector<vector<int>> edge;
vector<int> sz;
vector<int> que;
vector<bool> ok;
vector<bool> is;
int _n;
void init(int n) {
_n = n;
edge.clear();
sz.clear();
is.clear();
ok.clear();
edge.resize(n + 1);
sz.resize(n + 1);
is.resize(n + 1);
ok.resize(n + 1);
}
int dfs(int u, int p) {
sz[u] = 1;
for(int v : edge[u])
if(v != p && ok[v])
sz[u] += dfs(v, u);
return sz[u];
}
int centroid(int u, int p, int n) {
for(int v : edge[u])
if(v != p && ok[v] && sz[v] > n / 2)
return centroid(v, u, n);
return u;
}
void go(int u, int p) {
que.push_back(u);
is[u] = 1;
for(int v : edge[u])
if(v != p && ok[v])
go(v, u);
}
int solve(int u) {
for(int a : que) {
is[a] = 0;
//cerr << "removing " << a << " from que\n";
}
que.clear();
int n = dfs(u, u);
if(n == 1)
return u;
//cerr << u << ' ' << sz[u] << '\n';
u = centroid(u, u, n);
//cerr << u << '\n';
dfs(u, u);
assert(sz[u] == n);
que.push_back(u);
is[u] = 1;
int cur = 0;
for(int v : edge[u]) {
//cerr << "owo " << sz[v] << ' ' << ok[v] << cur + sz[v] << ' ' << n / 2 << '\n';
if(ok[v] && cur + sz[v] <= n / 2)
go(v, u), cur += sz[v];
}
if(n == 2) {
int x = que.back();
que.pop_back();
if(query(que))
return que[0];
else
return x;
}
//cerr << cur << '\n';
assert(!que.empty());
int w = query(que);
if(w) {
for(int i = 1; i <= _n; i++)
if(!is[i]) {
ok[i] = 0;
//cerr << "deletea " << i << '\n';
}
//cerr << "owo " << que[0] << '\n';
return solve(u);
}
else {
//cerr << "xdd " << que.size() << '\n';
for(int a : que) {
ok[a] = 0;
//cerr << "deleteb " << a << '\n';
}
for(int v : edge[u])
if(!is[v])
return solve(v);
}
assert(0);
return 0;
}
int findEgg(int n, vector<pair<int, int>> edges) {
init(n);
//cerr << "here\n";
for(int i = 1; i <= n; i++)
ok[i] = 1;
//cerr << "here\n";
for(const auto &[a, b] : edges)
edge[a].push_back(b), edge[b].push_back(a);
//cerr << "here\n";
return solve(1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
324 KB |
Number of queries: 5 |
| 2 |
Runtime error |
1 ms |
424 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
200 KB |
Number of queries: 9 |
| 2 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
16 ms |
328 KB |
Number of queries: 10 |
| 2 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
