oj.uz

Submission #87065

# Submission time Handle Problem Language Result Execution time Memory
87065 2018-11-29T10:41:35 Z report Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 36 ms 712 KB 
#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.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 252 KB Number of queries: 4
2 Correct 2 ms 452 KB Number of queries: 4
3 Correct 2 ms 452 KB Number of queries: 4
4 Correct 2 ms 532 KB Number of queries: 4

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 532 KB Number of queries: 8
2 Correct 31 ms 532 KB Number of queries: 9
3 Correct 32 ms 628 KB Number of queries: 9
4 Correct 36 ms 656 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 656 KB Number of queries: 9
2 Correct 25 ms 656 KB Number of queries: 9
3 Correct 24 ms 656 KB Number of queries: 9
4 Correct 28 ms 712 KB Number of queries: 9