Submission #522035

#	Time	Username	Problem	Language	Result	Execution time	Memory
522035		iskhakkutbilim	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	19 ms	448 KiB

eastereggs

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

using namespace std;

vector<int> g[515];

vector<int> island;
void dfs(int v, int par){
	island.push_back(v);
	for(auto to : g[v]){
		if(to == par) continue;
			dfs(to, v);
		
	}
}


int findEgg (int N, vector < pair < int, int > > bridges)
{
	
	for(int i = 1;i <= N; i++){
		g[i].clear();
	}
	island.clear();
	for(int i = 0;i < N-1; i++){
		int a = bridges[i].first;
		int b = bridges[i].second;
		g[a].push_back(b);
		g[b].push_back(a);
	}
   	dfs(1, -1);
   	//cout << 't';
   	// for(auto x : qu){
		// cout << x << " ";
	// }
	// cout << "\n";
//    	
	int l = 0, r = island.size()-1;
	while(r > l){
		int m = (l + r) / 2;
		vector<int> st;
		for(int i = 0;i <= m; i++){
			st.push_back(island[i]);
		}
		if(query(st)){
			r = m;
		}else l = m + 1;
	}
   	return island[l];
}

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