Submission #522031

#	Time	Username	Problem	Language	Result	Execution time	Memory
522031		iskhakkutbilim	Easter Eggs (info1cup17_eastereggs)	C++14	0 / 100	1 ms	456 KiB

eastereggs

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

using namespace std;

vector<int> g[515];
vector<int> used;
vector<int> island;
void dfs(int v){
	used[v] = 1;
	for(auto to : g[v]){
		if(used[to] == 0){
			dfs(to);
		}
	}
}


int findEgg (int N, vector < pair < int, int > > bridges)
{
	
	for(int i = 1;i <= N; i++){
		g[i].clear();
	}
	island.clear();
	used.resize(N + 2, 0);
	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);
   	//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: 0 / 40
• Subtask 2: 0 / 40
• Subtask 3: 0 / 20