#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]) 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(i);
}
}
}
}
array<int, 2> decide(int v)
{
val[v]=-1;
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]+=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[2]-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)
{
all=n=N;
for(auto i: bridges)
{
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
// int pf=10;
while(all>1)
{
findroot();
}
for(int i=1; i<=N&&ans; i++)
{
if(de[i]==0) ans=i;
}
return ans;
}
Compilation message
eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:12:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
12 | if(de[v]==0) ;
| ^~
eastereggs.cpp:13:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
13 | {
| ^
eastereggs.cpp: In function 'void dfs2(int, int)':
eastereggs.cpp:41:26: warning: unused variable 'l' [-Wunused-variable]
41 | for(auto l: zort[i]) zort[v].push_back(i);
| ^
eastereggs.cpp: In function 'std::array<int, 2> decide(int)':
eastereggs.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=1; i<q.size(); i++)
| ~^~~~~~~~~
eastereggs.cpp: In function 'void findroot()':
eastereggs.cpp:171: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]
171 | for(int i=1; i<qq.size(); i++)
| ~^~~~~~~~~~
eastereggs.cpp:159:17: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
159 | if(abs((a[1]+a[2]-1)-qq[0][0])<=abs(a[0]-a[1]))
eastereggs.cpp:131:18: note: while referencing 'a'
131 | array<int,2> a{1, 1};
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
688 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1256 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
