Submission #1139572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139572		tkm_algorithms	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	460 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;

vector<int> g[520], obhod(520, -1);
int c;

int findEgg (int N, vector < pair < int, int > > bridges) {
	for (auto i: bridges) {
		g[i.first].push_back(i.second);
		g[i.second].push_back(i.first);
	}
	
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		obhod[++c] = u;
		for (auto i: g[u])
			if (obhod[i] == -1)q.push(i);
	}
	
	int l = 0, r = N+1;
	while (r-l>1) {
		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;
		else l = mid;
	}
	return obhod[r];
}

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