#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
vector<int> adj[513], de(513), val(513), zort[513];
int n, all, ans=-1;
void dfs(int v, int p)
{
val[v]=0;
if(de[v]==0)
{
for(auto i: adj[v])
{
if(i==p||de[i]==1) continue;
dfs(i, v);
val[v]+=val[i];
}
val[v]++;
}
}
void dfs2(int v, int p)
{
zort[v].clear();
zort[v].push_back(v);
if(de[v]==0)
{
for(auto i: adj[v])
{
if(i==p||de[i]) continue;
dfs2(i, v);
if(p!=v)
{
for(auto l: zort[i]) zort[v].push_back(l);
}
}
}
}
array<int, 2> decide(int v)
{
val[v]=0;
dfs(v, v);
vector<int> q;
for(int i=0; i<=n; i++) zort[i].clear();
for(auto i: adj[v])
{
if(de[i]) continue;
q.push_back(val[i]);
}
sort(q.begin(), q.end());
reverse(q.begin(), q.end());
array<int, 2> h={1, 1};
for(auto i: q)
{
if(abs((h[0]+i)-h[1])<=abs((h[0])-(h[1]+i)))
{
h[0]+=i;
}
else
{
h[1]+=i;
}
}
array<int, 2> p={0, 1};
p[0]=q[0];
for(int i=1; i<q.size(); i++)
{
p[1]+=q[i];
}
if(abs(p[0]-p[1])<=abs(h[0]-h[1])) h=p;
return h;
}
void findroot()
{
array<int, 2> q{(int)1e9, 0};
int ind =0;
for(int i=1; i<=n; i++)
{
if(de[i]==0)
{
auto p=decide(i);
if((abs(p[1]-p[0])<=abs(q[1]-q[0]))||((abs(p[1]-p[0])==abs(q[1]-q[0]))&&q[1]+q[0]>p[1]+p[0]))
{
ind = i;
q=p;
}
}
}
dfs2(ind, ind);
vector<array<int, 2>> qq;
for(auto i: adj[ind])
{
if(de[i]) continue;
qq.push_back({(int)zort[i].size(), i});
}
sort(qq.begin(), qq.end());
reverse(qq.begin(), qq.end());
vector<int> h0, h1;
array<int,2> a={1, 1};
h1.push_back(ind);
h0.push_back(ind);
for(auto i: qq)
{
if(abs((a[0]+i[0])-a[1])<abs(a[0]-(a[1]+i[0])))
{
for(auto l: zort[i[1]])
{
h0.push_back(l);
}
a[0]+=i[0];
}
else
{
for(auto l: zort[i[1]])
{
h1.push_back(l);
}
a[1]+=i[0];
}
}
if(abs((a[1]+a[0]-1)-qq[0][0])<=abs(a[0]-a[1]))
{
h0.clear();
h1.clear();
for(auto i: zort[qq[0][1]])
{
h0.push_back(i);
}
h1.push_back(ind);
for(int i=1; i<qq.size(); i++)
{
for(auto l: zort[qq[i][1]])
{
h0.push_back(l);
}
}
}
if(all==2)
{
vector<int> f;
for(int i=1; i<=n; i++)
{
if(de[i]==0) f.push_back(i);
}
h1.clear();
h0.clear();
h1.push_back(f[0]);
h0.push_back(f[1]);
}
for(int i=0; i<=n; i++) de[i]=1;
all=0;
int p=query(h0);
if(p)
{
for(auto i: h0)
{
all++;
de[i]=0;
}
}
else
{
for(auto i: h1)
{
all++;
de[i]=0;
}
}
}
int findEgg(int N, vector < pair < int, int > > bridges)
{
for(int i=0; i<=N; i++) de[i]=val[i]=0;
all=N;
for(int i=1; i<=N; i++) adj[i].clear();
ans=-1;
all=n=N;
for(auto i: bridges)
{
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
while(all>1)
{
findroot();
}
for(int i=1; i<=N; i++)
{
if(de[i]==0) ans=i;
}
return ans;
}
Compilation message
eastereggs.cpp: In function 'std::array<int, 2> decide(int)':
eastereggs.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int i=1; i<q.size(); i++)
| ~^~~~~~~~~
eastereggs.cpp: In function 'void findroot()':
eastereggs.cpp:176:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
176 | for(int i=1; i<qq.size(); i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
2 ms |
208 KB |
Number of queries: 5 |
| 2 |
Partially correct |
2 ms |
208 KB |
Number of queries: 5 |
| 3 |
Partially correct |
2 ms |
208 KB |
Number of queries: 5 |
| 4 |
Partially correct |
2 ms |
208 KB |
Number of queries: 5 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
336 KB |
Number of queries: 9 |
| 2 |
Partially correct |
131 ms |
372 KB |
Number of queries: 10 |
| 3 |
Partially correct |
302 ms |
336 KB |
Number of queries: 11 |
| 4 |
Partially correct |
214 ms |
348 KB |
Number of queries: 10 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
378 ms |
720 KB |
Number of queries: 10 |
| 2 |
Partially correct |
274 ms |
336 KB |
Number of queries: 10 |
| 3 |
Partially correct |
320 ms |
336 KB |
Number of queries: 11 |
| 4 |
Partially correct |
225 ms |
336 KB |
Number of queries: 10 |
