Submission #1053002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053002		tolbi	Keys (IOI21_keys)	C++17	Compilation error	0 ms	0 KiB

keys

#include <bits/stdc++.h>
using namespace std;
struct DSU{
	vector<int> sz;
	vector<int> par;
	DSU(int n){
		sz.resize(n,1);
		par.resize(n);
		iota(par.begin(), par.end(), 0);
	}
	int find(int node){
		if (par[node]==node) return node;
		return par[node]=find(par[node]);
	}
	void merge(int a, int b){
		sz[b]+=sz[a];
		sz[a]=0;
		par[a]=b;
	}
};
struct node{
	set<int> keys;
	map<int,vector<int>> roads;
	vector<int> to;
	bool operator<(const node &ot)const{
		return (keys.size()+roads.size()+to.size())<(ot.keys.size()+ot.roads.size()+ot.to.size());
	};
	void process(){
		vector<int> sil;
		for (auto [k,it] : roads){
			if (keys.find(k)!=keys.end()){
				sil.push_back(k);
				for (auto it2 : it){
					to.push_back(it2);
				}
			}
		}
		for (auto it : sil) roads.erase(it);
	}
};
vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) {
	int n = r.size();
	vector<int> par(n);
	iota(par.begin(), par.end(), 0);
	DSU dsu(n);
	DSU compress(n);
	vector<node> arr(n);
	for (int i = 0; i < n; i++){
		arr[i].keys.insert(r[i]);
	}
	for (int i = 0; i < u.size(); ++i)
	{
		arr[u[i]].roads[c[i]].push_back(v[i]);
		arr[v[i]].roads[c[i]].push_back(u[i]);
	}
	queue<int> process;
	for (int i = 0; i < n; ++i)
	{
		arr[i].process();
		process.push(i);
	}
	while (process.size()){
		int node = process.front();
		process.pop();
		if (par[node]!=node) continue;
		while (arr[node].to.size()){
			int git = arr[node].to.back();
			arr[node].to.pop_back();
			if (dsu.find(git)==node){
				git=compress.find(git);
				while (git!=node){
					compress.merge(git,node);
					if (arr[git]>arr[node]) swap(arr[git],arr[node]);
					while (arr[git].to.size()){
						arr[node].to.push_back(arr[git].to.back());
						arr[git].to.pop_back();
					}
					for (auto it : arr[git].keys){
						if (arr[node].roads.count(it)){
							for (auto &hh : arr[node].roads[it]){
								arr[node].to.push_back(hh);
							}
							arr[node].roads.erase(it);
						}
						arr[node].keys.insert(it);
					}
					for (auto [k,it] : arr[git].roads){
						if (arr[node].keys.find(k)!=arr[node].keys.end()){
							for (auto &it2 : it){
								arr[node].to.push_back(it2);
							}
						}
						else {
							for (auto &it2 : it){
								arr[node].roads[k].push_back(it2);
							}
						}
					}
					git=compress.find(par[git]);
				}
			}
			else {
				dsu.merge(node,git);
				par[node]=git;
				process.push(dsu.find(node));
				break;
			}
		}
	}

	vector<int> ans;
	int sz;
	for (int i = 0; i < n; i++){
		if (dsu.find(i)==i){
			if (ans.size()==0 || compress.sz[i]<sz){
				ans.clear();
				sz=compress.sz[i];
				ans.push_back(i);
			}
			else if (compress.sz[i]==sz){
				ans.push_back(i);
			}
		}
	}
	vector<int> ret(n,0);
	for (auto it : ans) ret[it]=1;
	for (int i = 0; i < n; ++i)
	{
		if (ret[compress.find(i)]) ret[i]=1;	
	}
	return ret;
}

Compilation message (stderr)

keys.cpp: In function 'std::vector<int> find_reachable(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
keys.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < u.size(); ++i)
      |                  ~~^~~~~~~~~~
keys.cpp:73:18: error: no match for 'operator>' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} and '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'})
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1108:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
 1108 |     operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1108:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1168:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
 1168 |     operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1168:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1261:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
 1261 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1261:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1335:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
 1335 |     operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1335:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1429:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
 1429 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1429:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1505:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
 1505 |     operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1505:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/regex:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
                 from keys.cpp:1:
/usr/include/c++/10/bits/regex.h:1605:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
 1605 |     operator>(const sub_match<_Bi_iter>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1605:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::sub_match<_BiIter>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from keys.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:502:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
  502 |     operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:502:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::pair<_T1, _T2>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from keys.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
  378 |     operator>(const reverse_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:378:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::reverse_iterator<_Iterator>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from keys.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  416 |     operator>(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:416:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::reverse_iterator<_Iterator>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from keys.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1469 |     operator>(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::move_iterator<_IteratorL>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from keys.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
 1519 |     operator>(const move_iterator<_Iterator>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::move_iterator<_IteratorL>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/string_view:563:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
  563 |     operator> (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:563:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/string_view:569:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
  569 |     operator> (basic_string_view<_CharT, _Traits> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:569:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/bits/basic_string.h:48,
                 from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/string_view:576:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
  576 |     operator> (__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
      |     ^~~~~~~~
/usr/include/c++/10/string_view:576:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   'node' is not derived from 'std::basic_string_view<_CharT, _Traits>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6305:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6305 |     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6305:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6318:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
 6318 |     operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6318:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   '__gnu_cxx::__alloc_traits<std::allocator<node>, node>::value_type' {aka 'node'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included from /usr/include/c++/10/string:55,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from keys.cpp:1:
/usr/include/c++/10/bits/basic_string.h:6330:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
 6330 |     operator>(const _CharT* __lhs,
      |     ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6330:5: note:   template argument deduction/substitution failed:
keys.cpp:73:27: note:   mismatched types 'const _CharT*' and 'node'
   73 |      if (arr[git]>arr[node]) swap(arr[git],arr[node]);
      |                           ^
In file included f