#include <bits/stdc++.h>
#include "grader.h"
#define ll long long
#define vll vector<ll>
#define vllp vector<pair<ll, ll> >
#define vi vector <int>
#define vip vector <pair <int, int> >
#define db double
#define ld long double
#define pdb pair <double, double>
#define YES cout<<"YES"
#define NO cout<<"NO"
#define nl cout<<"\n"
#define vv vector <vector <ll> >
#define pll pair <ll, ll>
#define pi pair <int, int>
#define pb push_back
#define f first
#define s second
using namespace std;
const ll mod=1e9+7;
const ll modx=998244353;
const double eps=1e-9;
const ll INF=INT_MAX;
const ll INFINF=LLONG_MAX;
const int M=512;
vi vc[M+5], nodes;
int sz[M+5], pa[M+5];
bool bad[M+5];
void dfs(int u, int par)
{
sz[u]=1;
for(auto i: vc[u])
{
if(i==par) continue;
if(bad[i]) continue;
pa[i]=u;
dfs(i, u);
sz[u]+=sz[i];
}
}
int centroid_decom(int u, int size)
{
pi p={0, 0};
for(auto i: vc[u])
{
if(i==pa[u]) continue;
if(bad[i]) continue;
p=max(p, {sz[i], i});
}
if(p.f > size/2) return centroid_decom(p.s, size);
else return u;
}
void find(int u, int pa)
{
nodes.pb(u);
for(auto i: vc[u])
{
if(i==pa) continue;
find(i, u);
}
}
int findEgg(int N, vip bridges)
{
for(int i = 1; i <= N; i++) bad[i]=false, vc[i].clear();
for(auto i: bridges)
{
vc[i.f].pb(i.s);
vc[i.s].pb(i.f);
}
int u=1;
while(true)
{
nodes.clear();
if(N==2)
{
nodes.pb(u);
int report=query(nodes);
if(report) return u;
else
{
for(auto i: vc[u])
{
if(!bad[i]) return i;
}
}
}
dfs(u, 0);
pa[u]=0;
u=centroid_decom(u, N);
int sum=1;
vi node;
nodes.pb(u);
for(auto i: vc[u])
{
if(i==pa[u]) continue;
if(bad[i]) continue;
bad[i]=true;
sum+=sz[i];
find(i, u);
node.pb(i);
if(sum>=N/2) break;
}
int report=query(nodes);
N-=sum;
N++;
if(report)
{
for(auto i: vc[u])
{
if(!bad[i]) bad[i]^=1;
}
for(auto i: node)
{
bad[i]^=1;
}
N=sum;
}
// for(auto i: nodes) cout << i << " ";
// nl;
// cout << N << " " << sum << " " << u << "\n" << flush;
// for(int i = 1; i <= 5; i++) cout << bad[i] << " ";
// nl;
// cout << flush;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1 ms |
208 KB |
Number of queries: 5 |
| 2 |
Partially correct |
1 ms |
304 KB |
Number of queries: 6 |
| 3 |
Partially correct |
1 ms |
208 KB |
Number of queries: 6 |
| 4 |
Partially correct |
2 ms |
208 KB |
Number of queries: 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
348 KB |
Number of queries: 9 |
| 2 |
Partially correct |
8 ms |
336 KB |
Number of queries: 12 |
| 3 |
Partially correct |
14 ms |
336 KB |
Number of queries: 12 |
| 4 |
Partially correct |
9 ms |
336 KB |
Number of queries: 14 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
19 ms |
388 KB |
Number of queries: 10 |
| 2 |
Partially correct |
10 ms |
336 KB |
Number of queries: 13 |
| 3 |
Partially correct |
13 ms |
336 KB |
Number of queries: 12 |
| 4 |
Partially correct |
11 ms |
352 KB |
Number of queries: 13 |
