| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 983092 | vjudge1 | 사이버랜드 (APIO23_cyberland) | C++17 | 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 <vector>
#include <queue>
#include <limits>
using namespace std;
double solve(int N, int M, int K, int H, vector<int> x, vector<int> y, vector<int> c, vector<int> arr) {
// Initialize priority queue (min heap)
priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<tuple<double, int, int>>> pq;
// Initialize distance array
vector<double> distance(N, numeric_limits<double>::max());
distance[0] = 0; // Starting vertex
// Push starting vertex into priority queue
pq.push({0, 0, K}); // (time, vertex, remaining_divide_by_2)
// Dijkstra's algorithm
while (!pq.empty()) {
auto [cur_time, cur_vertex, cur_divide_by_2] = pq.top();
pq.pop();
if (cur_vertex == H) return cur_time; // Reached Cyberland
// Check all neighboring vertices
for (int i = 0; i < M; ++i) {
if (x[i] == cur_vertex || y[i] == cur_vertex) {
int neighbor = (x[i] == cur_vertex) ? y[i] : x[i];
// Calculate time considering special ability
double new_time = cur_time + c[i];
if (arr[neighbor] == 2 && cur_divide_by_2 > 0) {
new_time /= 2.0;
pq.push({new_time, neighbor, cur_divide_by_2 - 1});
} else if (arr[neighbor] == 1) {
pq.push({new_time, neighbor, cur_divide_by_2});
}
// Update distance array if shorter path found
if (new_time < distance[neighbor]) {
distance[neighbor] = new_time;
}
}
}
}
// Cyberland is not reachable
return -1;
}
Compilation message (stderr)
cyberland.cpp: In function 'double solve(int, int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
cyberland.cpp:16:22: error: no matching function for call to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::push(<brace-enclosed initializer list>)'
16 | pq.push({0, 0, K}); // (time, vertex, remaining_divide_by_2)
| ^
In file included from /usr/include/c++/10/queue:64,
from cyberland.cpp:2:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::tuple<double, int, int>&'}
640 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::value_type&&' {aka 'std::tuple<double, int, int>&&'}
648 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
cyberland.cpp:20:14: error: 'std::tuple<double, int, int> <structured bindings>' has incomplete type
20 | auto [cur_time, cur_vertex, cur_divide_by_2] = pq.top();
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cyberland.cpp:34:70: error: no matching function for call to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::push(<brace-enclosed initializer list>)'
34 | pq.push({new_time, neighbor, cur_divide_by_2 - 1});
| ^
In file included from /usr/include/c++/10/queue:64,
from cyberland.cpp:2:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::tuple<double, int, int>&'}
640 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::value_type&&' {aka 'std::tuple<double, int, int>&&'}
648 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
cyberland.cpp:36:66: error: no matching function for call to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::push(<brace-enclosed initializer list>)'
36 | pq.push({new_time, neighbor, cur_divide_by_2});
| ^
In file included from /usr/include/c++/10/queue:64,
from cyberland.cpp:2:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
640 | push(const value_type& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::tuple<double, int, int>&'}
640 | push(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::tuple<double, int, int>]'
648 | push(value_type&& __x)
| ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::tuple<double, int, int>, std::vector<std::tuple<double, int, int> >, std::greater<std::tuple<double, int, int> > >::value_type&&' {aka 'std::tuple<double, int, int>&&'}
648 | push(value_type&& __x)
| ~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/10/vector:67,
from cyberland.cpp:1:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >]':
/usr/include/c++/10/bits/stl_vector.h:487:7: required from 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = std::vector<std::tuple<double, int, int> >; _Requires = void; _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >]'
cyberland.cpp:9:112: required from here
/usr/include/c++/10/bits/stl_vector.h:336:35: error: invalid use of incomplete type 'class std::tuple<double, int, int>'
336 | _M_impl._M_end_of_storage - _M_impl._M_start);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from cyberland.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<double, int, int>'
2631 | class tuple;
| ^~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/vector:60,
from cyberland.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h: In substitution of 'template<class _IteratorL, class _IteratorR, class _Container> decltype ((__lhs.base() - __rhs.base())) __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&) [with _IteratorL = std::tuple<double, int, int>*; _IteratorR = std::tuple<double, int, int>*; _Container = std::vector<std::tuple<double, int, int> >]':
/usr/include/c++/10/bits/stl_heap.h:327:18: required from 'void std::pop_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::tuple<double, int, int>*, std::vector<std::tuple<double, int, int> > >; _Compare = std::greater<std::tuple<double, int, int> >]'
/usr/include/c++/10/bits/stl_queue.h:678:15: required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >]'
cyberland.cpp:21:16: required from here
/usr/include/c++/10/bits/stl_iterator.h:1166:30: error: invalid use of incomplete type 'class std::tuple<double, int, int>'
1166 | -> decltype(__lhs.base() - __rhs.base())
| ~~~~~~~~~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from cyberland.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'class std::tuple<double, int, int>'
2631 | class tuple;
| ^~~~~
In file included from /usr/include/c++/10/vector:67,
from cyberland.cpp:1:
/usr/include/c++/10/bits/stl_vector.h: In instantiation of 'void std::vector<_Tp, _Alloc>::pop_back() [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >]':
/usr/include/c++/10/bits/stl_queue.h:679:12: required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >]'
cyberland.cpp:21:16: required from here
/usr/include/c++/10/bits/stl_vector.h:1228:18: error: cannot decrement a pointer to incomplete type 'std::tuple<double, int, int>'
1228 | --this->_M_impl._M_finish;
| ~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from cyberland.cpp:1:
/usr/include/c++/10/type_traits: In instantiation of 'struct std::is_destructible<std::tuple<double, int, int> >':
/usr/include/c++/10/bits/stl_construct.h:177:51: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<double, int, int>*]'
/usr/include/c++/10/bits/alloc_traits.h:738:15: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<double, int, int>*; _Tp = std::tuple<double, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15: required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >]'
/usr/include/c++/10/bits/stl_queue.h:456:11: required from here
/usr/include/c++/10/type_traits:844:52: error: static assertion failed: template argument must be a complete class or an unbounded array
844 | static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/vector:65,
from cyberland.cpp:1:
/usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<double, int, int>*]':
/usr/include/c++/10/bits/alloc_traits.h:738:15: required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<double, int, int>*; _Tp = std::tuple<double, int, int>]'
/usr/include/c++/10/bits/stl_vector.h:680:15: required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >]'
/usr/include/c++/10/bits/stl_queue.h:456:11: required from here
/usr/include/c++/10/bits/stl_construct.h:177:51: error: static assertion failed: value type is destructible
177 | static_assert(is_destructible<_Value_type>::value,
| ^~~~~
/usr/include/c++/10/bits/stl_construct.h:184:25: error: invalid use of incomplete type 'std::iterator_traits<std::tuple<double, int, int>*>::value_type' {aka 'class std::tuple<double, int, int>'}
184 | std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/bits/move.h:57,
from /usr/include/c++/10/bits/stl_pair.h:59,
from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/vector:60,
from cyberland.cpp:1:
/usr/include/c++/10/type_traits:2631:11: note: declaration of 'std::iterator_traits<std::tuple<double, int, int>*>::value_type' {aka 'class std::tuple<double, int, int>'}
2631 | class tuple;
| ^~~~~
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.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::deallocate(_Tp*, __gnu_cxx::new_allocator<_Tp>::size_type) [with _Tp = std::tuple<double, int, int>; __gnu_cxx::new_allocator<_Tp>::size_type = long unsigned int]':
/usr/include/c++/10/bits/alloc_traits.h:492:23: required from 'static void std::allocator_traits<std::allocator<_Tp1> >::deallocate(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, std::allocator_traits<std::allocator<_Tp1> >::pointer, std::allocator_traits<std::allocator<_Tp1> >::size_type) [with _Tp = std::tuple<double, int, int>; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<std::tuple<double, int, int> >; std::allocator_traits<std::allocator<_Tp1> >::pointer = std::tuple<double, int, int>*; std::allocator_traits<std::allocator<_Tp1> >::size_type = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:354:19: required from 'void std::_Vector_base<_Tp, _Alloc>::_M_deallocate(std::_Vector_base<_Tp, _Alloc>::pointer, std::size_t) [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >; std::_Vector_base<_Tp, _Alloc>::pointer = std::tuple<double, int, int>*; std::size_t = long unsigned int]'
/usr/include/c++/10/bits/stl_vector.h:335:2: required from 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<double, int, int>; _Alloc = std::allocator<std::tuple<double, int, int> >]'
/usr/include/c++/10/bits/stl_vector.h:487:7: required from 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = std::vector<std::tuple<double, int, int> >; _Requires = void; _Tp = std::tuple<double, int, int>; _Sequence = std::vector<std::tuple<double, int, int> >; _Compare = std::greater<std::tuple<double, int, int> >]'
cyberland.cpp:9:112: required from here
/usr/include/c++/10/ext/new_allocator.h:123:6: error: invalid application of '__alignof__' to incomplete type 'std::tuple<double, int, int>'
123 | if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
| ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:127:16: error: invalid application of 'sizeof' to incomplete type 'std::tuple<double, int, int>'
127 | __t * sizeof(_Tp),
| ^~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:129:27: error: invalid application of '__alignof__' to incomplete type 'std::tuple<double, int, int>'
129 | std::align_val_t(alignof(_Tp)));
| ^~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:135:14: error: invalid application of 'sizeof' to incomplete type 'std::tuple<double, int, int>'
135 | , __t * sizeof(_Tp)
| ^~~~~~~~~~~