Submission #649402

#	Time	Username	Problem	Language	Result	Execution time	Memory
649402		berr	Easter Eggs (info1cup17_eastereggs)	C++17	0 / 100	8 ms	2000 KiB

eastereggs

#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];
		}

		if(adj[v].size()==1&&adj[v][0]==p) val[v]=1;
	}
}

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(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(query(h0))
	{
		for(auto i: h1)
		{
			all--;
			de[i]=1;
		}
	}
	else
	{
		for(auto i: h0)
		{
			all--;
			de[i]=1;
		}
	}



}


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);
	}

	while(all>1)
	{
		findroot();

	}

	for(int i=1; i<=N; i++)
	{
		if(de[i]==0) ans=i;
	}

	return ans;
}

Compilation message (stderr)

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:12:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   12 |  if(de[v]==0) ;
      |  ^~
eastereggs.cpp:13:2: 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:17: 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:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i=1; i<q.size(); i++)
      |               ~^~~~~~~~~
eastereggs.cpp: In function 'void findroot()':
eastereggs.cpp:168:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   for(int i=1; i<qq.size(); i++)
      |                ~^~~~~~~~~~
eastereggs.cpp:156:14: warning: array subscript 2 is outside array bounds of 'std::array<int, 2> [1]' [-Warray-bounds]
  156 |  if(abs((a[1]+a[2]-1)-qq[0][0])<=abs(a[0]-a[1]))
eastereggs.cpp:130:15: note: while referencing 'a'
  130 |  array<int,2> a{1, 1};
      |               ^

• Subtask 1: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20