Submission #1155936

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

eastereggs

#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 == 1) {
			return 1;
		}
	}
	return 0;
}
*/
int query(vector < int > islands);

vector<bool> vis;
vector<int> node;
vector<vector<int>> g;
ll n;
bool done_finding_right_nodes = false;

void dfs(ll start, ll count_node, vector<int>& maybe_nodes) {
	vis[start] = true;
	maybe_nodes.push_back(start);

	if (maybe_nodes.size() == count_node) {
		done_finding_right_nodes = true;
		/*we have reached half the nodes*/
		int answer = query(maybe_nodes);
		/*if our half doesnt contain the easter egg then take the other half*/
		if (answer == 0) {
			vector<bool> vis_for_maybe(n, true);
			for (auto i : maybe_nodes) {
				vis_for_maybe[i] = false;
			}
			vector<int> real_nodes;
			for (auto i : node) {
				if (vis_for_maybe[i]) {
					real_nodes.push_back(i);
				}
			}
			maybe_nodes = real_nodes;
			return;
		}
	}

	for (auto i : g[start]) {
		if (!vis[i]) {
			dfs(i, count_node, maybe_nodes);
			if (done_finding_right_nodes) {
				return;
			}
		}
	}
}

int findEgg(int N, vector<pair<int, int>> bridges) {
	n = N;
	vis.resize(n);
	g.resize(n);
	for (ll i = 0; i < n; i++) {
		vis[i] = false;
		node.push_back(i);
	}
	for (ll i = 0; i < n - 1; i++) {
		bridges[i].first--, bridges[i].second--;
		g[bridges[i].first].push_back(bridges[i].second);
		g[bridges[i].second].push_back(bridges[i].first);
	}
	while (node.size() > 1) {
		done_finding_right_nodes = false;
		vector<int> temp;
		for (ll i = 0; i < n; i++) {
			if (!vis[i]) {
				dfs(i, (node.size() / 2), temp);
				node.clear();
				node = temp;
				break;
			}
		}
		vis.clear();
		vis.resize(n, true);
		for (auto i : node) {
			vis[i] = false;
		}
	}
	return node[0]  + 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