Submission #98557

#	Time	Username	Problem	Language	Result	Execution time	Memory
98557		mohammedehab2002	Easter Eggs (info1cup17_eastereggs)	C++11	100 / 100	32 ms	384 KiB

eastereggs

#include <iostream>
#include "grader.h"
#include <vector>
using namespace std;
vector<int> v[515],t;
void dfs(int node,int p)
{
	t.push_back(node);
	for (int u:v[node])
	{
		if (u!=p)
		dfs(u,node);
	}
}
bool check(int m)
{
	vector<int> tmp;
	for (int i=0;i<=m;i++)
	tmp.push_back(t[i]);
	return query(tmp);
}
int findEgg(int n,vector<pair<int,int> > e)
{
	if (t.empty())
	{
		for (auto p:e)
		{
			v[p.first].push_back(p.second);
			v[p.second].push_back(p.first);
		}
		dfs(1,0);
	}
	int st=0,en=n-1;
	while (st!=en)
	{
		int mid=(st+en)/2;
		if (check(mid))
		en=mid;
		else
		st=mid+1;
	}
	return t[st];
}

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