Submission #1147206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147206		henriess	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	8 ms	512 KiB

eastereggs

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

using namespace std;

vector<int> vis;

vector<int> ord = {0};
vector<vector<int>> adjlist;
void dfs(int u,int p ){
    for(auto x : adjlist[u]){
		if (x == p){
			continue;
		}
		ord.push_back(x);
		dfs(x,u);
		
	}

}
int findEgg (int N, vector < pair < int, int > > bridges)
{	
	vis.assign(N, 0); // or fill(vis.begin(), vis.end(), 0);
	adjlist.assign(N, {});
	ord.clear();
	ord.push_back(0); // if you want to re-init
	
	for(int i = 0;i<N-1;i++){
		int a = bridges[i].first;
		int b = bridges[i].second;
		a--;b--;
		adjlist[a].push_back(b);
		adjlist[b].push_back(a);
	}
	
	dfs(0,-1);
	long long lb = 0;
	long long ub = N-1;
	long long mid = -1;
	long long ans = -1;
	while (lb < ub){
		mid = (lb + ub) / 2;
		vector<int> temp;
		for(int i = 0;i<=mid;i++){
			temp.push_back(ord[i] + 1);
		}
		int r = query(temp);
		if (r == 0){
			lb = mid + 1;
		}
		else{
			ub = mid;
		}
		
	}
	return ord[lb] + 1;
}

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