#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// int query(vector<int> h)
using namespace std;
int findEgg (int N, vector < pair < int, int > > bridges) {
vector<int> sz(N+1);
vector<bool> ban(N+1);
vector<vector<int>> edge(N+1);
for (auto [a, b] : bridges)
edge[a].pb(b), edge[b].pb(a);
while (true) {
int S = 0, R = -1;
for (int i = 1;i <= N;++i) {
if (!ban[i]) {
R = i;
++S;
}
}
if (S == 1) return R;
DE(S, R);
// I need to clear thing in edge
function<int(int,int)> dfs = [&](int x, int lst) {
sz[x] = 1;
for (int u : edge[x]) if (u != lst)
sz[x] += dfs(u, x);
return sz[x];
};
function<int(int,int)> get_cen = [&](int x, int lst) {
for (int u : edge[x]) if (u != lst)
if (sz[u] * 2 > S)
return get_cen(u, x);
return x;
};
vector<int> con;
function<void(int,int)> get_child = [&](int x, int lst) {
con.pb(x);
for (int u : edge[x]) if (u != lst)
get_child(u, x);
};
dfs(R, R);
int rt = get_cen(R, R);
dfs(rt, rt);
sort(AI(edge[rt]), [&](int a, int b) {
return sz[a] > sz[b];
});
int sum = 1, mid = S / 2;
con.pb(rt);
for (int u : edge[rt]) {
int ns = sum + sz[u];
if (abs(ns - mid) >= abs(sum - mid)) break;
get_child(u, rt);
sum += sz[u];
}
DE(S, sum);
if (query(con)) {
vector<bool> good(N+1);
for (int u : con) good[u] = true;
for (int i = 1;i <= N;++i)
if (!good[i]) ban[i] = true;
}
else {
for (int u : con) ban[u] = true;
}
for (int i = 1;i <= N;++i) {
int sz = 0;
for (int u : edge[i])
if (!ban[u])
edge[i][sz++] = u;
edge[i].resize(sz);
}
}
assert(false);
}
Compilation message
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define DE(...) 0
| ^
eastereggs.cpp:42:3: note: in expansion of macro 'DE'
42 | DE(S, R);
| ^~
eastereggs.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define DE(...) 0
| ^
eastereggs.cpp:86:3: note: in expansion of macro 'DE'
86 | DE(S, sum);
| ^~
| # |
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: 5 |
| 3 |
Partially correct |
2 ms |
200 KB |
Number of queries: 8 |
| 4 |
Partially correct |
1 ms |
200 KB |
Number of queries: 8 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
200 KB |
Number of queries: 9 |
| 2 |
Partially correct |
13 ms |
328 KB |
Number of queries: 15 |
| 3 |
Partially correct |
20 ms |
328 KB |
Number of queries: 18 |
| 4 |
Runtime error |
2 ms |
452 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
20 ms |
328 KB |
Number of queries: 10 |
| 2 |
Partially correct |
18 ms |
328 KB |
Number of queries: 13 |
| 3 |
Partially correct |
20 ms |
328 KB |
Number of queries: 19 |
| 4 |
Runtime error |
3 ms |
456 KB |
Execution killed with signal 6 |
