// {{{1
extern "C" int __lsan_is_turned_off() { return 1; }
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <deque>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define infl 0x3f3f3f3f3f3f3f3f
#ifdef DEBUG
#define dprintf(args...) fprintf(stderr,args)
#include <assert.h>
#endif
#ifndef DEBUG
#define dprintf(args...) 69
#define assert(args...) 42
#endif
// 1}}}
int query(vector<int> islands);
int findEgg(int n, vector<pair<int,int>> edges) {
for(auto&[a,b]:edges)a--,b--;
vector<vector<int>> adj(n);
for(auto [a,b]:edges) adj[a].push_back(b),adj[b].push_back(a);
set<int> vs;
for(int i=0;i<n;i++)vs.insert(i);
auto dfs = [&](auto& self, int u, int p) -> int {
if(!vs.count(u))return 0;
int sz=1;
for(auto x:adj[u])if(x!=p)sz+=self(self,x,u);
return sz;
};
auto doquery = [&](int u, int p) {
deque<int> dq;
dq.push_back(u);
vector<bool> vis(n);
vector<int> q;
while(dq.size()) {
int v=dq.front(); dq.pop_front();
if(vis[v])continue;
if(!vs.count(v))continue;
vis[v]=1;
q.push_back(1+v);
for(auto x:adj[v])if(x!=p)dq.push_back(x);
}
//for(auto j:q)printf("%d ",j);
int x=query(q);
//printf("%d\n",x);
for(auto&j:q)j--;
if(x) vs = set<int>{q.begin(),q.end()};
else for(auto jj:q)vs.erase(jj);
};
while(vs.size()&~1) {
//for(auto x:vs)printf("%d ",x);
//printf("\t\t%d\n\n\n",vs.size());
for (auto [u,v]: edges) {
//printf("try edge %d %d\n",u,v);
if(vs.count(u)&&vs.count(v)) {
// mayb?
int sz=dfs(dfs,u, v);
//printf("sz=%d\n",sz);
if(sz==vs.size()/2 || sz==vs.size()/2+1) {
//printf("q!\n");
doquery(u,v);
goto nxt;
}
}
}
assert(0);
nxt:;
}
return 1+*vs.begin();
}
#undef DEBUG
#ifdef DEBUG
int main()
{
}
#endif
Compilation message
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:33:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
33 | for(auto&[a,b]:edges)a--,b--;
| ^
eastereggs.cpp:36:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | for(auto [a,b]:edges) adj[a].push_back(b),adj[b].push_back(a);
| ^
eastereggs.cpp:73:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | for (auto [u,v]: edges) {
| ^
eastereggs.cpp:79:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(sz==vs.size()/2 || sz==vs.size()/2+1) {
| ~~^~~~~~~~~~~~~
eastereggs.cpp:79:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if(sz==vs.size()/2 || sz==vs.size()/2+1) {
| ~~^~~~~~~~~~~~~~~
eastereggs.cpp:26:25: warning: statement has no effect [-Wunused-value]
26 | #define assert(args...) 42
| ^~
eastereggs.cpp:86:17: note: in expansion of macro 'assert'
86 | assert(0);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
208 KB |
Number of queries: 5 |
| 2 |
Execution timed out |
3071 ms |
208 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
336 KB |
Number of queries: 9 |
| 2 |
Execution timed out |
3063 ms |
336 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
218 ms |
336 KB |
Number of queries: 10 |
| 2 |
Execution timed out |
3089 ms |
336 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
