Submission #67874

#	Time	Username	Problem	Language	Result	Execution time	Memory
67874		quoriess	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	74 ms	696 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"
using namespace std;
const int MAXN=520;
typedef pair<int,int> pii;
vector<int> adj[MAXN];
vector<pii> dizi;
void doldur(int node,int parent){
	dizi.push_back(pii(parent,node));
	for (auto it:adj[node])
	{
		if(it==parent)continue;
		doldur(it,node);
	}
}
int findEgg (int N, vector < pair < int, int > > bridges)
{
	dizi.clear();
	for(int i=1;i<=N;i++){
		adj[i].clear();
	}
	for(int i=0;i<(int)bridges.size();i++){
		adj[bridges[i].first].push_back(bridges[i].second);
		adj[bridges[i].second].push_back(bridges[i].first);
	}
	doldur(1,-1);
	//cout<<" dizisi\n";
	int low=0,high=dizi.size()-1;
	int mid=(low+high)/2;
	int sol=-1;
	while(low<=high){
		mid=(low+high)/2;
		//cout << "low: "<<low<<" high: "<<high<<" mid: "<<mid<<"\n";
		set<int> distinct;
		if(sol==-1 && low==high){sol=mid;break;}
		for (int i = 0; i <= mid; i++)
		{
			if(dizi[i].first!=-1)distinct.insert(dizi[i].first);
			distinct.insert(dizi[i].second);
		}
		vector<int> sorg;	
		
		for (auto s:distinct)
		{
			sorg.push_back(s);
			//cout << s<<" ";
		}
		//cout<<"\n";
		if(query(sorg)){
			high=mid-1;
			sol=mid;
		}
		else low=mid+1;
	}
	return dizi[sol].second;
}

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