#include <bits/stdc++.h>
#include "grader.h"
#define MAXN 550
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using namespace std;
static int N, X, cntQ;
static vector < int > v[1009];
typedef pair < int , int > ii;
typedef vector < int > vi;
// int query (vector < int > h)
// {
// cntQ ++;
// int ap[1009];
// if (h.empty ()) return 0;
// for (int i=1; i<=N; i++)
// ap[i] = 0;
// for (vi::iterator it = h.begin (); it != h.end (); it ++)
// ap[*it] = 1;
// queue < int > cc;
// cc.push (h[0]), ap[h[0]] = 2;
// while (!cc.empty ())
// {
// int nod = cc.front ();
// cc.pop ();
// for (vi::iterator it = v[nod].begin (); it != v[nod].end (); it ++)
// if (ap[*it] == 1)
// ap[*it] = 2, cc.push (*it);
// }
// for (int i=1; i<=N; i++)
// if (ap[i] == 1) return -1;
// for (vi::iterator it = h.begin (); it != h.end (); it ++)
// if (*it == X) return 1;
// return 0;
// }
int n = -1, ans, u[MAXN], h[MAXN], say;
vi g[MAXN], sor;
void dfs(int node, int par, int kac){
if(say >= kac)
return;
sor.pb(node);
if(u[node])
say++;
if(say >= kac)
return;
for(int i = 0; i < g[node].size(); i++)
if(g[node][i] != par)
dfs(g[node][i], node, kac);
}
void bul(int node, int kac){
if(kac == 1){
for(int i = 1; i <= n; i++)
if(u[i]){
ans = i;
return;
}
}
sor.clear();
say = 0;
dfs(node, 0, kac/2);
// for(int i = 0; i < sor.size(); i++)cout << sor[i] << " ";cout << endl;
if(query(sor)){
if(sor.size() == 1){
ans = sor[0];
return;
}
memset(h, 0, sizeof h);
for(int i = 0; i < sor.size(); i++)
h[sor[i]] = 1;
for(int i = 1; i <= n; i++)
if(!h[i])
u[i] = 0;
bul(node, kac/2);
}else{
for(int i = 0; i < sor.size(); i++)
u[sor[i]] = 0;
bul(node, kac - kac/2);
}
}
int findEgg (int N, vector < ii > b){
for(int i = 1; i <= N; i++)
u[i] = 1;
if(n == -1)
for(int i = 0; i < b.size(); i++){
g[b[i].st].pb(b[i].nd);
g[b[i].nd].pb(b[i].st);
}
ans = -1;
n = N;
bul(1, n);
return ans;
}
// int main ()
// {
// freopen ("in.txt", "r", stdin);
// freopen ("out.txt", "w", stdout);
// scanf ("%d", &N);
// int Queries;
// vector < pair < int, int > > param;
// for (int i=1; i<N; i++)
// {
// int x, y;
// scanf ("%d %d", &x, &y);
// v[x].push_back (y);
// v[y].push_back (x);
// param.push_back (mp(x, y) );
// }
// scanf ("%d", &Queries);
// while (Queries --)
// {
// scanf ("%d", &X), cntQ = 0;
// int Y = findEgg (N, param);
// if (X != Y)
// {
// printf ("WA %d instead of %d\n", Y, X);
// return 0;
// }
// printf ("OK %d\n", cntQ);
// }
// return 0;
// }
Compilation message
eastereggs.cpp: In function 'void dfs(int, int, int)':
eastereggs.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'void bul(int, int)':
eastereggs.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < sor.size(); i++)
~~^~~~~~~~~~~~
eastereggs.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < sor.size(); i++)
~~^~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < b.size(); i++){
~~^~~~~~~~~~
eastereggs.cpp: At global scope:
eastereggs.cpp:12:18: warning: 'cntQ' defined but not used [-Wunused-variable]
static int N, X, cntQ;
^~~~
eastereggs.cpp:12:15: warning: 'X' defined but not used [-Wunused-variable]
static int N, X, cntQ;
^
eastereggs.cpp:12:12: warning: 'N' defined but not used [-Wunused-variable]
static int N, X, cntQ;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Number of queries: 4 |
| 2 |
Correct |
2 ms |
440 KB |
Number of queries: 4 |
| 3 |
Correct |
3 ms |
504 KB |
Number of queries: 4 |
| 4 |
Correct |
4 ms |
580 KB |
Number of queries: 4 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
580 KB |
Number of queries: 8 |
| 2 |
Correct |
26 ms |
580 KB |
Number of queries: 9 |
| 3 |
Correct |
44 ms |
608 KB |
Number of queries: 9 |
| 4 |
Correct |
21 ms |
608 KB |
Number of queries: 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
608 KB |
Number of queries: 9 |
| 2 |
Correct |
22 ms |
608 KB |
Number of queries: 9 |
| 3 |
Correct |
24 ms |
608 KB |
Number of queries: 9 |
| 4 |
Correct |
19 ms |
608 KB |
Number of queries: 9 |
