Submission #87065

#	Time	Username	Problem	Language	Result	Execution time	Memory
87065		report	Easter Eggs (info1cup17_eastereggs)	C++14	100 / 100	36 ms	712 KiB

eastereggs

#include <iostream>
#include <vector>
#include <algorithm>
#include "grader.h"

using namespace std;

void computeUnmarkedComponent(
		int n,
		const vector<int> &marked, 
		const vector<vector<int>> &tree, 
		vector<int> &res) {
	int treeSize = (int)tree.size();
	queue<int> q;
	vector<bool> visited(treeSize);
	q.push(1);
	visited[1] = true;
	int unmarkedCnt = 0;
	while (!q.empty() && unmarkedCnt < n) {
		int u = q.front();
		q.pop();
		unmarkedCnt += !marked[u];
		res.push_back(u);
		for (int v : tree[u]) {
			if (!visited[v]) {
				visited[v] = true;
				q.push(v);
			}
		}
	}
	sort(res.begin(), res.end());
}

int findEgg(int N, vector<pair<int, int>> bridges) {
	vector<int> marked(N + 1);
	vector<vector<int>> tree(N + 1, vector<int>());
	for (const pair<int, int> &edge : bridges) {
		tree[edge.first].push_back(edge.second);
		tree[edge.second].push_back(edge.first);
	}
	vector<int> allNodes;
	for (int i = 1; i <= N; i++) allNodes.push_back(i);

	int unmarkedCnt = N;
	while (true) {
		if (unmarkedCnt == 1) {
			for (int i = 1; i <= N; i++) {
				if (!marked[i]) return i;
			}
			break;
		}
		vector<int> component;
		computeUnmarkedComponent(unmarkedCnt / 2, marked, tree, component);
		vector<int> toMark;
		if (query(component)) {
			toMark.resize(N - (int)component.size());
			set_difference(allNodes.begin(), allNodes.end(), 
				component.begin(), component.end(), toMark.begin());
			unmarkedCnt /= 2;
		} else {
			toMark = component;
			unmarkedCnt -= unmarkedCnt / 2;
		}
		for (int n : toMark) {
			marked[n] = true;
		}
	}
	return 0;
}

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