oj.uz

답안 #471218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
471218 2021-09-07T16:48:51 Z BlancaHM Easter Eggs (info1cup17_eastereggs) C++14
0 / 100
 1 ms 456 KB 
#include <iostream>
#include <vector>
#include <map>
#include <unordered_set>
#include <algorithm>
#include <set>
#include <queue>
#include "grader.h"
using namespace std;

void reset(set<int> & possibleLocations, vector<pair<int, int>> & edges, vector<vector<int>> & adjList) {
	int N = (int) edges.size() + 1;
	adjList = vector<vector<int>>(N);
	for (int i = 0; i < N; i++)
		possibleLocations.insert(i); // We add the island to the remaining possibilities
    for (int i = 0; i < N-1; i++) {
        // We add the edge to the adjacency list
        adjList[edges[i].first - 1].push_back(edges[i].second - 1);
        adjList[edges[i].second - 1].push_back(edges[i].first - 1);
	}
}

// Query about the selected half and discard the appropriate half after the query response
set<int> & reduceRemaining(set<int> & currentSelection, set<int> & possibleLocations) {
	vector<int> queryIslands;
	set<int> nextPossibleLocations;

	for (auto it = currentSelection.begin(); it != currentSelection.end(); it++)
		queryIslands.push_back(*it + 1);

	if (query(queryIslands) == 1) {
		// selectedIslands = intersection of possibleLocations and currentSelection
		for (int island: possibleLocations)
			if (currentSelection.find(island) != currentSelection.end())
				nextPossibleLocations.insert(island);
	} else {
		// selectedIslands = intersection of possibleLocations and NOT currentSelection
		for (int island: possibleLocations)
			if (currentSelection.find(island) == currentSelection.end())
				nextPossibleLocations.insert(island);
	}

	return nextPossibleLocations;
}

set<int> & selectHalf(set<int> & possibleLocations, vector<vector<int>> & adjList) {
    int root = *possibleLocations.begin();

    // Do BFS starting on the root until we have selected half of the possible egg locations
    // Note: as the islands in the query must be connected, we may include in the query other islands which we know do not contain the egg
    queue<int> Q;
	Q.push(root);

    int selectedIslands = 1; // Number of islands selected which are possible egg locations
    int possibleIslands = (int) possibleLocations.size();

    set<int> currentSelection; // Islands selected for the next query, including previously discarded ones
    currentSelection.insert(root);

    while (!Q.empty()) {
        if (selectedIslands * 2 >= possibleIslands)
            break; // We already have 1/2 of the possible egg locations

        // Otherwise, continue with the DFS
        int currentIsland = Q.front();
        Q.pop();

        // Iterate over the neighbouring islands
        for (int neighbour : adjList[currentIsland]) {
            if (selectedIslands * 2 >= possibleIslands)
                break;
            if (currentSelection.find(neighbour) == currentSelection.end()) {
                // Have not selected this island for the query yet-> we select it
                currentSelection.insert(neighbour);
                Q.push(neighbour);
                if (possibleLocations.find(neighbour) != possibleLocations.end())
                    selectedIslands++; // this island is a possible egg location
            }
        }
    }
    return currentSelection;
}

int findEgg(int N, vector<pair<int, int>> edges) {
	vector<vector<int>> adjList;
	set<int> possibleLocations, currentSelection;
	reset(possibleLocations, edges, adjList);
	queue<int> Q;
	while((int) possibleLocations.size() > 1) {
        currentSelection = selectHalf(possibleLocations, adjList);
		// Process our current selection, reducing the possible locations set to 1/2 its previous size
		possibleLocations = reduceRemaining(currentSelection, possibleLocations);
	}
	return *possibleLocations.begin() + 1;
}

Compilation message

eastereggs.cpp: In function 'std::set<int>& reduceRemaining(std::set<int>&, std::set<int>&)':
eastereggs.cpp:43:9: warning: reference to local variable 'nextPossibleLocations' returned [-Wreturn-local-addr]
   43 |  return nextPossibleLocations;
      |         ^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp:26:11: note: declared here
   26 |  set<int> nextPossibleLocations;
      |           ^~~~~~~~~~~~~~~~~~~~~
eastereggs.cpp: In function 'std::set<int>& selectHalf(std::set<int>&, std::vector<std::vector<int> >&)':
eastereggs.cpp:81:12: warning: reference to local variable 'currentSelection' returned [-Wreturn-local-addr]
   81 |     return currentSelection;
      |            ^~~~~~~~~~~~~~~~
eastereggs.cpp:57:14: note: declared here
   57 |     set<int> currentSelection; // Islands selected for the next query, including previously discarded ones
      |              ^~~~~~~~~~~~~~~~

Subtask #1
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -