Submission #1164609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164609		boclobanchat	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	492 KiB

eastereggs

#include<bits/stdc++.h>
#include"grader.h"
using namespace std;
vector<int> ds[555];
int eul[555],tdfs=0;
void dfs(int i,int pre)
{
	eul[++tdfs]=i;
	for(auto v:ds[i]) if(v!=pre) dfs(v,i);
}
int findEgg(int N,vector< pair<int,int> > bridges)
{
	for(auto v:bridges) ds[v.first].push_back(v.second),ds[v.second].push_back(v.first);
	dfs(1,1);
	int l=1,r=N,ans=0;
	while(l<r)
	{
		int mid=(l+r)/2;
		vector<int> pos;
		for(int i=1;i<=mid;i++) pos.push_back(eul[i]);
		bool ck=(r-l==1);
		if(query(pos)) r=mid,ans=mid;
		else l=mid+1,ans=mid+1;
	}
	for(int i=1;i<=N;i++) ds[i].clear();
	tdfs=0;
	return eul[ans];
}

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