Submission #243041

#	Time	Username	Problem	Language	Result	Execution time	Memory
243041		HachiMinh	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	26 ms	384 KiB

eastereggs

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef vector<int> vct;
vct HMS[600],USS;
void dfs(int u,int pa)
{
	USS.pb(u);
	for(int i=0;i<HMS[u].size();i++)
	{
		int d=HMS[u][i];
		if(d!=pa)
		{
			dfs(d,u);
		}
	}
}
int check(int mid)
{
	vector<int> KMS;
	for(int i=0;i<=mid;i++)
	{
		KMS.pb(USS[i]);
	}
	return query(KMS);
}
int findEgg(int N,vector<pair<int,int> >bridges)
{
	USS.clear();
	for(int i=0;i<N-1;i++)
	{
		int u=bridges[i].fi,v=bridges[i].se;
		HMS[u].pb(v);
		HMS[v].pb(u);
	}
	dfs(1,0);
	int l=0,r=USS.size()-1;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	for(int i=0;i<N+7;i++) HMS[i].clear();
	return USS[l];
}

Compilation message (stderr)

eastereggs.cpp: In function 'void dfs(int, int)':
eastereggs.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<HMS[u].size();i++)
              ~^~~~~~~~~~~~~~

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