Submission #1139579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139579		tkm_algorithms	Easter Eggs (info1cup17_eastereggs)	C++20	100 / 100	9 ms	480 KiB

eastereggs

/**
*    In the name of Allah
*    We are nothing and you're everything
*    author: najmuddin
**/

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

using namespace std;

int findEgg (int N, vector < pair < int, int > > bridges) {
	vector<int> g[520], obhod(520, -1);
	int c = 0;

	for (auto i: bridges) {
		g[i.first].push_back(i.second);
		g[i.second].push_back(i.first);
	}
	
	queue<pair<int, int>> q;
	q.push({1, -1});
	while (!q.empty()) {
		auto u = q.front();
		q.pop();
		obhod[++c] = u.first;
		for (auto i: g[u.first])
			if (i != u.second)q.push({i, u.first});
	}
	
	int l = 1, r = N-1;
	int ans = N;
	while (l <= r) {
		int mid = (l + r) >> 1;
		//assert(mid >=1 && mid <= N);
		vector<int> a;
		for (int i = 1; i <= mid; ++i)
			a.push_back(obhod[i]);
		if (query(a) == 1)r = mid-1, ans = mid;
		else l = mid+1;
	}
	return obhod[ans];
}

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