답안 #384575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
384575	2021-04-01T21:00:50 Z	BlancaHM	Easter Eggs (info1cup17_eastereggs)	C++14	컴파일 오류	0 ms	0 KB

eastereggs

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include "grader.h"
using namespace std;


void init(set<int> & islandsLeft, vector <pair<int,int>> & bridges, vector<vector<int>> & adj) {
	int N = (int) bridges.size()+1;
	islandsLeft = set<int>();
	for (int i = 0; i < N; i++) {
		islandsLeft.insert(i);
		if (i) {
			bridges[i - 1].first--;
			bridges[i - 1].second--;
			adj[bridges[i - 1].first].push_back(bridges[i - 1].second);
			adj[bridges[i - 1].second].push_back(bridges[i - 1].first);
		}
	}
}

vector<int> process(set<int> & curQ, set<int> & islandsLeft) {
	vector<int> queryVec, nextIs;
	for (auto it = curQ.begin(); it != curQ.end(); it++)
		queryVec.push_back(*it);
	if (query(queryVec)) {
		// islands = intersection of islands and curQ
		nextIs.clear();
		for (int is : islandsLeft) {
			if (curQ.find(is) != curQ.end())
				nextIs.push_back(is);
		}
	} else {
		// islands = intersection of islands and NOT curQ
		nextIs.clear();
		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(N, vector<int>());
	set<int> islandsLeft, curQ;
	init(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 = vector<int>();
		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++;
				}
			}
		}
		// process islandsLeft
		vector<int> nextIs = process(curQ, islandsLeft);
		islandsLeft.clear();
		for (int is: nextIs)
			islandsLeft.insert(is);
	}
	return *islandsLeft.begin() + 1;
}

Compilation message

eastereggs.cpp: In function 'int findEgg(int, std::vector<std::pair<int, int> >)':
eastereggs.cpp:53:22: error: no match for 'operator=' (operand types are 'std::set<int>' and 'std::vector<int>')
   53 |   curQ = vector<int>();
      |                      ^
In file included from /usr/include/c++/9/set:61,
                 from eastereggs.cpp:3:
/usr/include/c++/9/bits/stl_set.h:298:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>& std::set<_Key, _Compare, _Alloc>::operator=(const std::set<_Key, _Compare, _Alloc>&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  298 |       operator=(const set&) = default;
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_set.h:298:17: note:   no known conversion for argument 1 from 'std::vector<int>' to 'const std::set<int>&'
  298 |       operator=(const set&) = default;
      |                 ^~~~~~~~~~
/usr/include/c++/9/bits/stl_set.h:94:11: note: candidate: 'std::set<_Key, _Compare, _Alloc>& std::set<_Key, _Compare, _Alloc>::operator=(std::set<_Key, _Compare, _Alloc>&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
   94 |     class set
      |           ^~~
/usr/include/c++/9/bits/stl_set.h:302:17: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::set<int>&&'
  302 |       operator=(set&&) = default;
      |                 ^~~~~
/usr/include/c++/9/bits/stl_set.h:316:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>& std::set<_Key, _Compare, _Alloc>::operator=(std::initializer_list<_Tp>) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  316 |       operator=(initializer_list<value_type> __l)
      |       ^~~~~~~~
/usr/include/c++/9/bits/stl_set.h:316:46: note:   no known conversion for argument 1 from 'std::vector<int>' to 'std::initializer_list<int>'
  316 |       operator=(initializer_list<value_type> __l)
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~