#include <bits/stdc++.h>
#include "grader.h"
/*
static int N, X, cntQ;
static vector < int > v[1009];
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 (auto 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 (auto 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 (auto it = h.begin (); it != h.end (); it ++)
if (*it == X) return 1;
return 0;
}*/
using namespace std;
vector<vector<int>> adj;
int findEgg (int n, vector < pair < int, int > > bridges)
{
adj.resize(n+1);
int temp,temp2;
for(temp=0;temp<bridges.size();temp++)
{
int x=bridges[temp].first,y=bridges[temp].second;
adj[x].push_back(y);
adj[y].push_back(x);
}
bool cntbisa[n+1]; int sisacnt=n;
memset(cntbisa,true,sizeof(cntbisa));
while(sisacnt>1)
{
//cout<<sisacnt<<"\n";
queue<int> q;
bool visited[n+1]; memset(visited,false,sizeof(visited));
q.push(1);
vector<int> stk;
while(!q.empty())
{
int pos=q.front();
q.pop();
visited[pos]=true;
if(cntbisa[pos])
{
stk.push_back(pos);
}
if(stk.size()>=sisacnt/2)
{
break;
}
for(temp=0;temp<adj[pos].size();temp++)
{
int thenode=adj[pos][temp];
if(visited[thenode]) continue;
q.push(thenode);
}
}
int lol=query(stk);
if(lol==1)
{
sisacnt=stk.size();
memset(cntbisa,0,sizeof(cntbisa));
for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=true;
}
else
{
sisacnt-=stk.size();
for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=false;
}
}
for(temp=1;temp<=n;temp++) if(cntbisa[temp]) return temp;
}
/*
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "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 ({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 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(temp=0;temp<bridges.size();temp++)
~~~~^~~~~~~~~~~~~~~
eastereggs.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(stk.size()>=sisacnt/2)
~~~~~~~~~~^~~~~~~~~~~
eastereggs.cpp:65:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(temp=0;temp<adj[pos].size();temp++)
~~~~^~~~~~~~~~~~~~~~
eastereggs.cpp:77:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=true;
~~~~^~~~~~~~~~~
eastereggs.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(temp=0;temp<stk.size();temp++) cntbisa[stk[temp]]=false;
~~~~^~~~~~~~~~~
eastereggs.cpp:36:14: warning: unused variable 'temp2' [-Wunused-variable]
int temp,temp2;
^~~~~
eastereggs.cpp:86:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
516 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
