제출 #67824

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
67824		quoriess	Easter Eggs (info1cup17_eastereggs)	C++14	81 / 100	72 ms	692 KiB

eastereggs

#include <bits/stdc++.h>
#include "grader.h"

using namespace std;
const int MAXN=520;
vector<int> adj[MAXN];
vector<int> dizi;
void doldur(int node,int parent){
	dizi.push_back(node);
	for (auto it:adj[node])
	{
		if(it==parent)continue;
		doldur(it,node);
		dizi.push_back(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;

		for (int i = 0; i <= mid; i++)
		{
			distinct.insert(dizi[i]);
		}
		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];
}

• Subtask 1: 32 / 40
• Subtask 2: 34 / 40
• Subtask 3: 15 / 20