#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, ans, u[MAXN], say[MAXN];
vi g[MAXN], sor;
void dfs(int node, int par){
sor.pb(node);
for(int i = 0; i < g[node].size(); i++)
if(!u[g[node][i]] and g[node][i] != par)
dfs(g[node][i], node);
}
int hazirla(int node, int par){
say[node] = 1;
for(int i = 0; i < g[node].size(); i++)
if(g[node][i] != par and !u[g[node][i]])
say[node] += hazirla(g[node][i], node);
// cout << node << " -> " << say[node] << endl;
return say[node];
}
void centbul(int node, int top){
hazirla(node, node);
int par = node, f = 1;
while(f){
f = 0;
for(int i = 0; i < g[node].size(); i++)
if(!u[g[node][i]] and g[node][i] != par and say[ g[node][i] ] > top/2){
par = node;
node = g[node][i];
f = 1;
break;
}
}
ii mx = mp(-1, -1);
for(int i = 0; i < g[node].size(); i++)
if(!u[g[node][i]] and g[node][i] != par){
int coc = g[node][i];
mx = max(mx, mp(say[coc], coc));
}
if(mx.st == -1){
sor.clear();
sor.pb(node);
if(query(sor)){
ans = node;
return;
}
}
sor.clear();
dfs(mx.nd, node);
if(query(sor)){
u[node] = 1;
centbul(mx.nd, mx.st);
} else{
u[mx.nd] = 1;
centbul(node, top - mx.st);
}
}
int findEgg (int N, vector < ii > b){
for(int i = 0; i < MAXN; i++){
say[i] = u[i] = 0;
g[i].clear();
}
ans = -1;
n = N;
for(int i = 0; i < b.size(); i++){
g[b[i].st].pb(b[i].nd);
g[b[i].nd].pb(b[i].st);
}
// hazirla(1, 1);
centbul(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)':
eastereggs.cpp:54:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int hazirla(int, int)':
eastereggs.cpp:62: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 centbul(int, int)':
eastereggs.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
eastereggs.cpp:83:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[node].size(); i++)
~~^~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:119:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < b.size(); i++){
~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
248 KB |
Number of queries: 5 |
| 2 |
Incorrect |
4 ms |
436 KB |
Number of queries: 6 |
| 3 |
Incorrect |
2 ms |
436 KB |
Number of queries: 10 |
| 4 |
Incorrect |
3 ms |
436 KB |
Number of queries: 16 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
496 KB |
Number of queries: 9 |
| 2 |
Incorrect |
11 ms |
512 KB |
Number of queries: 13 |
| 3 |
Incorrect |
9 ms |
544 KB |
Number of queries: 29 |
| 4 |
Runtime error |
4 ms |
768 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
768 KB |
Number of queries: 10 |
| 2 |
Incorrect |
12 ms |
768 KB |
Number of queries: 13 |
| 3 |
Incorrect |
18 ms |
800 KB |
Number of queries: 29 |
| 4 |
Runtime error |
6 ms |
800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
