Submission #1158099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158099		itaykarny	Easter Eggs (info1cup17_eastereggs)	C++20	0 / 100	0 ms	480 KiB

eastereggs

#include "grader.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<math.h>



using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pair<ll, ll>>;
using vvpll = vector<vpll>;


/*
int query(vector<int> t) {
	for (auto i : t) {
		if (i == 2) {
			return 1;
		}
	}
	return 0;
}*/

int query(vector < int > islands);

vector<vector<int>> g;
vector<int> nodes;
vector<bool> vis;

int n;

void dfs(ll start) {
	nodes.push_back(start);
	vis[start] = true;
	for (auto i : g[start]) {
		if (!vis[i]) {
			dfs(i);
		}
	}
}


int findEgg(int N, vector < pair < int, int > > bridges) {
	n = N;
	g.resize(n);
	vis.resize(n);
	for (ll i = 0; i < n - 1; i++) {
		g[--bridges[i].first].push_back(--bridges[i].second);
		g[bridges[i].second].push_back(bridges[i].first);
	}
	vector<int> ask, prev_ask;
	dfs(0);
	ll start = 0, end = n - 1;
	while (start < end) {
		ll mid = (start + end) / 2;
		for (ll i = start; i <= mid; i++) {
			ask.push_back(nodes[i]);
		}
		int answer = query(ask);
		if (answer == 0) {
			prev_ask = ask;
			start = mid + 1;
		}
		else {
			ask = prev_ask;
			end = mid;
		}
	}
	return nodes[end] + 1;
}
/*
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int s;
	cin >> s;
	vector<pair<int, int>> bridges(s-1);
	for (ll i = 0; i < s- 1; i++) {
		cin >> bridges[i].first >> bridges[i].second;
	}
	cout << findEgg(s, bridges);

}*/

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