oj.uz

Submission #384720

# Submission time Handle Problem Language Result Execution time Memory
384720 2021-04-02T06:26:55 Z BlancaHM Easter Eggs (info1cup17_eastereggs) C++14
100 / 100
 46 ms 612 KB 
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include "grader.h"
using namespace std;
 
/*
Variables:
islandsLeft
curQ
bridges
adj
queryVec
nextIs
q
 */
 
void reset(set<int> & islandsLeft, vector <pair<int,int>> & bridges, vector<vector<int>> & adj) {
	int N = (int) bridges.size()+1;
	adj.clear();
	adj.assign(N, vector<int>());
	islandsLeft = set<int>();
	islandsLeft.clear();
	for (int i = 0; i < N; i++) {
		islandsLeft.insert(i);
		if (i) {
			int a = bridges[i-1].first - 1, b = bridges[i-1].second - 1;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
	}
}
 
vector<int> process(set<int> & curQ, set<int> & islandsLeft) {
	vector<int> queryVec = vector<int>(), nextIs = vector<int>();
	queryVec.clear();
	nextIs.clear();
	for (auto it = curQ.begin(); it != curQ.end(); it++)
		queryVec.push_back(*it + 1);
	if (query(queryVec)) {
		// islands = intersection of islands and curQ
		for (int is : islandsLeft) {
			if (curQ.find(is) != curQ.end())
				nextIs.push_back(is);
		}
	} else {
		// islands = intersection of islands and NOT curQ
		for (int is : islandsLeft) {
			if (curQ.find(is) == curQ.end())
				nextIs.push_back(is);
		}
	}
	return nextIs;
}
 
int findEgg(int N, vector <pair<int,int>> bridges) {
	vector<vector<int>> adj;
	set<int> islandsLeft, curQ;
	reset(islandsLeft, bridges, adj);
	queue<int> q;
	while ((int) islandsLeft.size() > 1) {
		// hacemos un árbol que contenga la primera mitad de islas restantes y ninguna de la segunda mitad
		curQ = set<int>();
		curQ.clear();
		curQ.insert(*islandsLeft.begin());
		q = queue<int>();
		q.push(*islandsLeft.begin());
		int islands = 1;
		while(q.size()) {
			if (islands*2 >= (int) islandsLeft.size())
				break;
			int curIs = q.front();
			q.pop();
			for (int v: adj[curIs]) {
				if (islands*2 >= (int) islandsLeft.size()) break;
				if (curQ.find(v) == curQ.end()) {
					curQ.insert(v);
					q.push(v);
					if (islandsLeft.find(v) != islandsLeft.end())
						islands++;
				}
				if (islands*2 >= (int) islandsLeft.size()) break;
			}
		}
		// process islandsLeft
		vector<int> nextIs = process(curQ, islandsLeft);
		islandsLeft.clear();
		for (int is: nextIs)
			islandsLeft.insert(is);
	}
	return *islandsLeft.begin() + 1;
}

Subtask #1
40.0 / 40.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 364 KB Number of queries: 8
2 Correct 29 ms 436 KB Number of queries: 9
3 Correct 39 ms 492 KB Number of queries: 9
4 Correct 37 ms 364 KB Number of queries: 9

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 364 KB Number of queries: 9
2 Correct 38 ms 364 KB Number of queries: 9
3 Correct 39 ms 364 KB Number of queries: 9
4 Correct 46 ms 612 KB Number of queries: 9