| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983232 | 2024-05-15T09:38:38 Z | vjudge1 | Cyberland (APIO23_cyberland) | C++17 | Compilation error |
0 ms | 0 KB |
#include "cyberland.h"
#include <bits/stdc++.h>
using namespace std;
const double INF = numeric_limits<double>::max();
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr) {
vector<vector<pair<int, double>>> g(N);
for (int i = 0; i < M; ++i) {
g[x[i]].emplace_back(y[i], c[i]);
g[y[i]].emplace_back(x[i], c[i]);
}
vector<vector<double>> dis(N, vector<double>(K + 1, INF));
dis[0][0] = 0;
set<tuple<double, int, int>> q;
q.emplace(dis[0], 0, 0);
while (!q.empty()) {
auto [w, nearest, i] = *q.begin();
q.erase(q.begin());
for (auto [to, weight]: g[nearest]) {
if (!arr[to]) weight = -dis[nearest][i];
if (dis[to][i] > dis[nearest][i] + weight) {
q.erase(tuple{dis[to][i], to, i});
dis[to][i] = dis[nearest][i] + weight;
q.emplace(dis[to][i], to, i);
}
if (arr[to] == 2 && dis[to][i + 1] > (dis[nearest][i] + weight) / 2.) {
q.erase(tuple{dis[to][i + 1], to, i + 1});
dis[to][i + 1] = (dis[nearest][i] + weight) / 2.;
q.emplace(dis[to][i], to, i + 1);
}
}
}
double res = INF;
for (int i = 0; i <= K; ++i) res = min(dis[H][i], res);
return res;
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = std::tuple<double, int, int>; _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Tp = std::_Rb_tree_node<std::tuple<double, int, int> >]':
/usr/include/c++/10/bits/alloc_traits.h:512:17: required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = std::tuple<double, int, int>; _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Tp = std::_Rb_tree_node<std::tuple<double, int, int> >; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::_Rb_tree_node<std::tuple<double, int, int> > >]'
/usr/include/c++/10/bits/stl_tree.h:618:32: required from 'void std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_construct_node(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, _Args&& ...) [with _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Key = std::tuple<double, int, int>; _Val = std::tuple<double, int, int>; _KeyOfValue = std::_Identity<std::tuple<double, int, int> >; _Compare = std::less<std::tuple<double, int, int> >; _Alloc = std::allocator<std::tuple<double, int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::tuple<double, int, int> >*]'
/usr/include/c++/10/bits/stl_tree.h:635:21: required from 'std::_Rb_tree_node<_Val>* std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_create_node(_Args&& ...) [with _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Key = std::tuple<double, int, int>; _Val = std::tuple<double, int, int>; _KeyOfValue = std::_Identity<std::tuple<double, int, int> >; _Compare = std::less<std::tuple<double, int, int> >; _Alloc = std::allocator<std::tuple<double, int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::tuple<double, int, int> >*]'
/usr/include/c++/10/bits/stl_tree.h:2414:33: required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_emplace_unique(_Args&& ...) [with _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Key = std::tuple<double, int, int>; _Val = std::tuple<double, int, int>; _KeyOfValue = std::_Identity<std::tuple<double, int, int> >; _Compare = std::less<std::tuple<double, int, int> >; _Alloc = std::allocator<std::tuple<double, int, int> >]'
/usr/include/c++/10/bits/stl_set.h:463:33: required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Allocator>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::emplace(_Args&& ...) [with _Args = {std::vector<double, std::allocator<double> >&, int, int}; _Key = std::tuple<double, int, int>; _Compare = std::less<std::tuple<double, int, int> >; _Alloc = std::allocator<std::tuple<double, int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Allocator>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<std::tuple<double, int, int>, std::tuple<double, int, int>, std::_Identity<std::tuple<double, int, int> >, std::less<std::tuple<double, int, int> >, std::allocator<std::tuple<double, int, int> > >::const_iterator]'
cyberland.cpp:17:24: required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'std::tuple<double, int, int>::tuple(std::vector<double>&, int, int)'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:795:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
795 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:795:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: mismatched types 'std::tuple<_UTypes ...>' and 'int'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:783:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Args2 ...>&&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
783 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:783:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: mismatched types 'std::tuple<_UTypes ...>' and 'int'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:772:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
772 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:772:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: mismatched types 'const std::tuple<_UTypes ...>' and 'int'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:760:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Args2 ...>&) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<const _UElements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
760 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:760:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: mismatched types 'const std::tuple<_UTypes ...>' and 'int'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:752:2: note: candidate: 'template<class _Alloc> std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, std::tuple<_Elements>&&) [with _Alloc = _Alloc; _Elements = {double, int, int}]'
752 | tuple(allocator_arg_t __tag, const _Alloc& __a, tuple&& __in)
| ^~~~~
/usr/include/c++/10/tuple:752:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: cannot convert 'std::forward<std::vector<double>&>((* & __args#0))' (type 'std::vector<double>') to type 'std::allocator_arg_t'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:747:2: note: candidate: 'template<class _Alloc> std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const std::tuple<_Elements>&) [with _Alloc = _Alloc; _Elements = {double, int, int}]'
747 | tuple(allocator_arg_t __tag, const _Alloc& __a, const tuple& __in)
| ^~~~~
/usr/include/c++/10/tuple:747:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: cannot convert 'std::forward<std::vector<double>&>((* & __args#0))' (type 'std::vector<double>') to type 'std::allocator_arg_t'
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:740:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
740 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:740:2: note: template argument deduction/substitution failed:
/usr/include/c++/10/tuple:737:48: error: no type named 'type' in 'struct std::enable_if<false, bool>'
737 | _ExplicitCtor<_Valid, _UElements...> = false>
| ^~~~~
/usr/include/c++/10/tuple:730:2: note: candidate: 'template<class _Alloc, class ... _UElements, bool _Valid, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, _UElements&& ...) [with _Alloc = _Alloc; _UElements = {_UElements ...}; bool _Valid = _Valid; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
730 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:730:2: note: template argument deduction/substitution failed:
/usr/include/c++/10/tuple:728:48: error: no type named 'type' in 'struct std::enable_if<false, bool>'
728 | _ImplicitCtor<_Valid, _UElements...> = true>
| ^~~~
/usr/include/c++/10/tuple:722:2: note: candidate: 'template<class _Alloc, bool _NotEmpty, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_explicitly_constructible<const double&, const int&, const int&>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const _Elements& ...) [with _Alloc = _Alloc; bool _NotEmpty = _NotEmpty; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_explicitly_constructible<const _Elements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
722 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:722:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 5 arguments, 3 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:714:2: note: candidate: 'template<class _Alloc, bool _NotEmpty, typename std::enable_if<std::tuple<double, int, int>::_TCC<_Valid>::__is_implicitly_constructible<const double&, const int&, const int&>(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&, const _Elements& ...) [with _Alloc = _Alloc; bool _NotEmpty = _NotEmpty; typename std::enable_if<std::tuple<_Elements>::_TCC<_Valid>::__is_implicitly_constructible<const _Elements& ...>(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
714 | tuple(allocator_arg_t __tag, const _Alloc& __a,
| ^~~~~
/usr/include/c++/10/tuple:714:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/vector:64,
from cyberland.h:1,
from cyberland.cpp:1:
/usr/include/c++/10/ext/new_allocator.h:150:4: note: candidate expects 5 arguments, 3 provided
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from cyberland.cpp:3:
/usr/include/c++/10/tuple:708:2: note: candidate: 'template<class _Alloc, typename std::enable_if<std::tuple<double, int, int>::_TCC<std::is_object<_Tp>::value>::__is_implicitly_default_constructible(), bool>::type <anonymous> > std::tuple<_Elements>::tuple(std::allocator_arg_t, const _Alloc&) [with _Alloc = _Alloc; typename std::enable_if<std::tuple<_Elements>::_TCC<std::is_object<_Alloc>::value>::__is_implicitly_default_constructible(), bool>::type <anonymous> = <anonymous>; _Elements = {double, int, int}]'
708 | tuple(allocator_arg_t __tag, const _Alloc& __a)
| ^~~~~
/usr/include/c++/10/tuple:708:2: note: template argument deduction/substitution failed:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator