#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define test(x) cout << #x << ' ' << x << endl
#define printv(x) { \
for (auto a : x) cout << a << ' '; \
cout << endl; \
}
#define pii pair<int, int>
#define pll pair<lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
const int N = 513, abc = 864197532;
vector <int> adj[N];
int query(vector <int> islands);
int findEgg(int n, vector <pii> bridges) {
for (pii i : bridges) {
adj[i.X].pb(i.Y);
adj[i.Y].pb(i.X);
}
vector <bool> dead(n + 1, false);
dead[0] = true;
while (count(all(dead), false) > 1) {
n = count(all(dead), false);
vector <int> cur;
int not_dead_cnt = 0;
function<void(int, int)> dfs = [&](int v, int pa) {
if (not_dead_cnt < n / 2) cur.pb(v), not_dead_cnt += !dead[v];
for (int u : adj[v]) if (u != pa) {
dfs(u, v);
}
};
dfs(1, -1);
int ans = query(cur);
for (int i = 1; i < dead.size(); ++i) if (!dead[i] && count(all(cur), i) != ans) {
dead[i] = true;
}
}
return find(all(dead), true) - dead.begin();
}
Compilation message
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:43:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i = 1; i < dead.size(); ++i) if (!dead[i] && count(all(cur), i) != ans) {
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3067 ms |
332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3048 ms |
328 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
