| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 125212 | Sorting | Simurgh (IOI17_simurgh) | C++14 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "simurgh.h"
using namespace std;
//int count_common_roads(vector<int> &r);
const int N = 507;
const int M = N * (N - 1) / 2 + 1;
mt19937 mt;
int rnd(int mod){
return mt() % mod;
}
struct edge{
int from, to, idx, score;
edge();
edge(int from, int to, int idx){
this->from = from;
this->to = to;
this->idx = idx;
score = 0;
}
};
vector<int> adj[N];
vector<edge> ev;
int m, par[N], sz[N], r[M];
void find_par(int u){
if(u == par[u]){
return;
}
find_par(par[u]);
par[u] = par[par[u]];
}
bool unite(int u, int v){
find_par(u);
find_par(v);
if(par[u] == par[v]){
return false;
}
if(sz[par[u]] < sz[par[v]]){
swap(u, v);
}
sz[par[u]] += sz[par[v]];
par[par[v]] = par[u];
return true;
}
vector<int> find_roads(int n, vector<int> u, vector<int> v){
m = (int)u.size();
for(int i = 0; i < m; i++){
//adj[ u[i] ].push_back(v[i]);
//adj[ v[i] ].push_back(u[i]);
ev.push_back(edge(u[i], v[i], i));
}
for(int j = 0; j < 30000; j++){
for(int i = 0; i < n; i++){
par[i] = i;
sz[i] = 1;
}
for(int i = 0; i < m; i++){
ev[i].score = r[ev[i].idx];
}
if(j % 10){
random_shuffle(ev.begin(), ev.end(), rnd);
}
else{
sort(ev.begin(), ev.end());
}
vector<int> v;
for(edge e: ev){
if(unite(e.from, e.to)){
v.push_back(e.idx);
if(v.size() == n - 1){
break;
}
}
}
int ans = count_common_roads(v);
if(ans == n - 1){
return v;
}
for(int x: ans){
r[x] += ans;
}
}
}
Compilation message (stderr)
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:89:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size() == n - 1){
~~~~~~~~~^~~~~~~~
simurgh.cpp:101:14: error: 'begin' was not declared in this scope
for(int x: ans){
^~~
simurgh.cpp:101:14: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
from simurgh.cpp:1:
/usr/include/c++/7/valarray:1211:5: note: 'std::begin'
begin(const valarray<_Tp>& __va)
^~~~~
/usr/include/c++/7/valarray:1211:5: note: 'std::begin'
simurgh.cpp:101:14: error: 'end' was not declared in this scope
for(int x: ans){
^~~
simurgh.cpp:101:14: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:95:0,
from simurgh.cpp:1:
/usr/include/c++/7/valarray:1231:5: note: 'std::end'
end(const valarray<_Tp>& __va)
^~~
/usr/include/c++/7/valarray:1231:5: note: 'std::end'
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_less_iter::operator()(_Iterator1, _Iterator2) const [with _Iterator1 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Iterator2 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]':
/usr/include/c++/7/bits/stl_algo.h:81:17: required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1921:34: required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1953:38: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1968:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
simurgh.cpp:81:29: required from here
/usr/include/c++/7/bits/predefined_ops.h:43:23: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:43:23: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:43:23: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return *__it1 < *__it2; }
~~~~~~~^~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_less_iter::operator()(_Value&, _Iterator) const [with _Value = edge; _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]':
/usr/include/c++/7/bits/stl_algo.h:1828:20: required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Val_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1855:36: required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1885:25: required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1971:31: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
simurgh.cpp:81:29: required from here
/usr/include/c++/7/bits/predefined_ops.h:90:22: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return __val < *__it; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:90:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return __val < *__it; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:90:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return __val < *__it; }
~~~~~~^~~~~~~
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_less_val::operator()(_Iterator, _Value&) const [with _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Value = edge]':
/usr/include/c++/7/bits/stl_heap.h:133:48: required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Distance = long int; _Tp = edge; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
/usr/include/c++/7/bits/stl_heap.h:237:23: required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Distance = long int; _Tp = edge; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_heap.h:342:22: required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1672:23: required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1933:25: required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1948:27: required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:1968:25: required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
/usr/include/c++/7/bits/stl_algo.h:4836:18: required from 'void std::sort(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >]'
simurgh.cpp:81:29: required from here
/usr/include/c++/7/bits/predefined_ops.h:65:22: error: no match for 'operator<' (operand types are 'edge' and 'edge')
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: candidate: template<class _IteratorL, class _IteratorR, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)
operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:888:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~
In file included from /usr/include/c++/7/bits/stl_algobase.h:67:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: candidate: template<class _Iterator, class _Container> bool __gnu_cxx::operator<(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)
operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
^~~~~~~~
/usr/include/c++/7/bits/stl_iterator.h:895:5: note: template argument deduction/substitution failed:
In file included from /usr/include/c++/7/bits/stl_algobase.h:71:0,
from /usr/include/c++/7/bits/char_traits.h:39,
from /usr/include/c++/7/ios:40,
from /usr/include/c++/7/istream:38,
from /usr/include/c++/7/sstream:38,
from /usr/include/c++/7/complex:45,
from /usr/include/c++/7/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
from simurgh.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h:65:22: note: 'edge' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
{ return *__it < __val; }
~~~~~~^~~~~~~
simurgh.cpp:105:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^