Submission #1158899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158899		countless	Cyberland (APIO23_cyberland)	C++20	Compilation error	0 ms	0 KiB

cyberland

#include "cyberland.h"

#include <vector>
#include <queue>
#include <iostream>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const ld INF = 9e18;

// this should work for k <= 30
ld divByPow2(ll x, ll k) {
    return (ld)x / (ld)pow(2, k);
}

// pretty sure this works too
void checkReal(int start, int H, vector<vector<pair<ll, ll>>> &adj, vector<bool> &real) {
    real[start] = true;

    if (start == H) return;

    for (const pair<ll, ll> &i : adj[start]) {
        if (!real[i.first]) {
            checkReal(i.first, H, adj, real);
        }
    }
}

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<ll, ll>>> adj(N+5);

    cerr << "arr: ";
    for (int i = 0; i < N; i++) {
        cerr << arr[i] << " ";
    }
    cerr << endl;

    for (int i = 0; i < M; i++) {
        adj[x[i]].push_back({y[i], c[i]});
        adj[y[i]].push_back({x[i], c[i]});
    }

    vector<bool> real(N+5, false);
    checkReal(0, H, adj, real);

    if (!real[H]) return -1;
    real[H] = false;

    vector<vector<ld>> dist(N+5, vector<ld>(K + 1 + 5, INF));
    dist[H][0] = 0;
    priority_queue<tuple<ld, ll, ll>, vector<tuple<ld, ll, ll>>, greater<tuple<ld, ll, ll>>> pq;
    pq.push(make_tuple((ld)0.0, 0LL, (ll)H));

    while (!pq.empty()) {
        // const auto [cdist, k, node] = pq.top();
        ld cdist = get<0>(pq.top());
        ll k = get<1>(pq.top());
        ll node = get<2>(pq.top());
        pq.pop();

        if (cdist > dist[node][k]) continue;

        if ((arr[node] == 0 || node == 0) && real[node]) {
            return cdist;
        }

        // if (cdist != dist[node][k]) continue;
        for (const pair<ll, ll> &i : adj[node]) {
            if (i.first == H) continue;
            if (!real[i.first]) continue;

            ld ndist1 = cdist + ((ld)i.second / (ld)pow(2.0, (ld)k));
            if (ndist1 < dist[i.first][k]) {
                dist[i.first][k] = ndist1;
                pq.push(make_tuple(dist[i.first][k], k, i.first));
            }
            
            if (arr[node] == 2 && k < K) {
                ld ndist2 = cdist + ((ld)i.second / (ld)pow(2.0, (ld)k + 1));
                if (ndist2 < dist[i.first][k+1]) {
                    dist[i.first][k+1] = ndist2;
                    pq.push(make_tuple(dist[i.first][k+1], k + 1, i.first));
                }
            }
        }
    }

    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:56:13: error: 'make_tuple' was not declared in this scope
   56 |     pq.push(make_tuple((ld)0.0, 0LL, (ll)H));
      |             ^~~~~~~~~~
cyberland.cpp:7:1: note: 'std::make_tuple' is defined in header '<tuple>'; did you forget to '#include <tuple>'?
    6 | #include <math.h>
  +++ |+#include <tuple>
    7 | 
cyberland.cpp:60:20: error: 'get' was not declared in this scope; did you mean 'getw'?
   60 |         ld cdist = get<0>(pq.top());
      |                    ^~~~~~
      |                    getw
In file included from /usr/include/c++/11/vector:67,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_vector.h: In instantiation of 'std::_Vector_base<_Tp, _Alloc>::~_Vector_base() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]':
/usr/include/c++/11/bits/stl_vector.h:487:7:   required from 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue() [with _Seq = std::vector<std::tuple<long double, long long int, long long int> >; _Requires = void; _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:55:94:   required from here
/usr/include/c++/11/bits/stl_vector.h:336:49: error: invalid use of incomplete type 'class std::tuple<long double, long long int, long long int>'
  336 |                       _M_impl._M_end_of_storage - _M_impl._M_start);
      |                       ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits:45:11: note: declaration of 'class std::tuple<long double, long long int, long long int>'
   45 |     class tuple;
      |           ^~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h: In instantiation of 'constexpr typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&) [with _Iterator = std::tuple<long double, long long int, long long int>*; _Container = std::vector<std::tuple<long double, long long int, long long int> >; typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type = long int]':
/usr/include/c++/11/bits/stl_heap.h:327:18:   required from 'constexpr void std::pop_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::tuple<long double, long long int, long long int>*, std::vector<std::tuple<long double, long long int, long long int> > >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:678:15:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/bits/stl_iterator.h:1271:27: error: invalid use of incomplete type 'class std::tuple<long double, long long int, long long int>'
 1271 |     { return __lhs.base() - __rhs.base(); }
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits:45:11: note: declaration of 'class std::tuple<long double, long long int, long long int>'
   45 |     class tuple;
      |           ^~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h: In instantiation of 'constexpr __gnu_cxx::__normal_iterator<_Iterator, _Container>& __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator--() [with _Iterator = std::tuple<long double, long long int, long long int>*; _Container = std::vector<std::tuple<long double, long long int, long long int> >]':
/usr/include/c++/11/bits/stl_heap.h:331:4:   required from 'constexpr void std::pop_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::tuple<long double, long long int, long long int>*, std::vector<std::tuple<long double, long long int, long long int> > >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:678:15:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/bits/stl_iterator.h:1068:11: error: cannot decrement a pointer to incomplete type 'std::tuple<long double, long long int, long long int>'
 1068 |         --_M_current;
      |           ^~~~~~~~~~
In file included from /usr/include/c++/11/vector:67,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_vector.h: In instantiation of 'void std::vector<_Tp, _Alloc>::pop_back() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]':
/usr/include/c++/11/bits/stl_queue.h:679:12:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/bits/stl_vector.h:1228:25: error: cannot decrement a pointer to incomplete type 'std::tuple<long double, long long int, long long int>'
 1228 |         --this->_M_impl._M_finish;
      |           ~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits: In instantiation of 'struct std::is_nothrow_destructible<std::tuple<long double, long long int, long long int> >':
/usr/include/c++/11/bits/alloc_traits.h:532:41:   required from 'static constexpr void std::allocator_traits<std::allocator<_Up> >::destroy(std::allocator_traits<std::allocator<_Up> >::allocator_type&, _Up*) [with _Up = std::tuple<long double, long long int, long long int>; _Tp = std::tuple<long double, long long int, long long int>; std::allocator_traits<std::allocator<_Up> >::allocator_type = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_vector.h:1229:24:   required from 'void std::vector<_Tp, _Alloc>::pop_back() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:679:12:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/type_traits:939:52: error: static assertion failed: template argument must be a complete class or an unbounded array
  939 |       static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/type_traits:939:52: note: 'std::__is_complete_or_unbounded<std::__type_identity<std::tuple<long double, long long int, long long int> > >((std::__type_identity<std::tuple<long double, long long int, long long int> >{}, std::__type_identity<std::tuple<long double, long long int, long long int> >()))' evaluates to false
/usr/include/c++/11/type_traits: In instantiation of 'struct std::is_destructible<std::tuple<long double, long long int, long long int> >':
/usr/include/c++/11/bits/stl_construct.h:188:51:   required from 'constexpr void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*]'
/usr/include/c++/11/bits/alloc_traits.h:848:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*; _Tp = std::tuple<long double, long long int, long long int>]'
/usr/include/c++/11/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:456:11:   required from here
/usr/include/c++/11/type_traits:885:52: error: static assertion failed: template argument must be a complete class or an unbounded array
  885 |       static_assert(std::__is_complete_or_unbounded(__type_identity<_Tp>{}),
      |                     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/type_traits:885:52: note: 'std::__is_complete_or_unbounded<std::__type_identity<std::tuple<long double, long long int, long long int> > >((std::__type_identity<std::tuple<long double, long long int, long long int> >{}, std::__type_identity<std::tuple<long double, long long int, long long int> >()))' evaluates to false
In file included from /usr/include/c++/11/bits/stl_iterator.h:85,
                 from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_construct.h: In instantiation of 'constexpr void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*]':
/usr/include/c++/11/bits/alloc_traits.h:848:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*; _Tp = std::tuple<long double, long long int, long long int>]'
/usr/include/c++/11/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:456:11:   required from here
/usr/include/c++/11/bits/stl_construct.h:188:51: error: static assertion failed: value type is destructible
  188 |       static_assert(is_destructible<_Value_type>::value,
      |                                                   ^~~~~
/usr/include/c++/11/bits/stl_construct.h:188:51: note: 'std::integral_constant<bool, false>::value' evaluates to false
/usr/include/c++/11/bits/stl_construct.h:195:25: error: invalid use of incomplete type 'using value_type = std::remove_cv_t<std::tuple<long double, long long int, long long int> >' {aka 'class std::tuple<long double, long long int, long long int>'}
  195 |       std::_Destroy_aux<__has_trivial_destructor(_Value_type)>::
      |                         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits:45:11: note: declaration of 'using value_type = std::remove_cv_t<std::tuple<long double, long long int, long long int> >' {aka 'class std::tuple<long double, long long int, long long int>'}
   45 |     class tuple;
      |           ^~~~~
In file included from /usr/include/c++/11/bits/stl_algo.h:61,
                 from /usr/include/c++/11/vector:62,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_heap.h: In instantiation of 'constexpr void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<std::tuple<long double, long long int, long long int>*, std::vector<std::tuple<long double, long long int, long long int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<std::greater<std::tuple<long double, long long int, long long int> > >]':
/usr/include/c++/11/bits/stl_heap.h:332:19:   required from 'constexpr void std::pop_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<std::tuple<long double, long long int, long long int>*, std::vector<std::tuple<long double, long long int, long long int> > >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:678:15:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/bits/stl_heap.h:261:18: error: '_ValueType __value' has incomplete type
  261 |       _ValueType __value = _GLIBCXX_MOVE(*__result);
      |                  ^~~~~~~
/usr/include/c++/11/bits/stl_heap.h:262:17: error: invalid use of incomplete type 'class std::tuple<long double, long long int, long long int>'
  262 |       *__result = _GLIBCXX_MOVE(*__first);
      |                 ^
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits:45:11: note: declaration of 'class std::tuple<long double, long long int, long long int>'
   45 |     class tuple;
      |           ^~~~~
In file included from /usr/include/c++/11/bits/stl_iterator.h:85,
                 from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/bits/stl_construct.h: In instantiation of 'static constexpr void std::_Destroy_aux<<anonymous> >::__destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*; bool <anonymous> = false]':
/usr/include/c++/11/bits/stl_construct.h:193:39:   required from 'constexpr void std::_Destroy(_ForwardIterator, _ForwardIterator) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*]'
/usr/include/c++/11/bits/alloc_traits.h:848:15:   required from 'void std::_Destroy(_ForwardIterator, _ForwardIterator, std::allocator<_T2>&) [with _ForwardIterator = std::tuple<long double, long long int, long long int>*; _Tp = std::tuple<long double, long long int, long long int>]'
/usr/include/c++/11/bits/stl_vector.h:680:15:   required from 'std::vector<_Tp, _Alloc>::~vector() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:456:11:   required from here
/usr/include/c++/11/bits/stl_construct.h:162:39: error: cannot increment a pointer to incomplete type 'std::tuple<long double, long long int, long long int>'
  162 |           for (; __first != __last; ++__first)
      |                                       ^~~~~~~
/usr/include/c++/11/bits/stl_construct.h: In instantiation of 'constexpr void std::destroy_at(_Tp*) [with _Tp = std::tuple<long double, long long int, long long int>]':
/usr/include/c++/11/bits/alloc_traits.h:537:19:   required from 'static constexpr void std::allocator_traits<std::allocator<_Up> >::destroy(std::allocator_traits<std::allocator<_Up> >::allocator_type&, _Up*) [with _Up = std::tuple<long double, long long int, long long int>; _Tp = std::tuple<long double, long long int, long long int>; std::allocator_traits<std::allocator<_Up> >::allocator_type = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_vector.h:1229:24:   required from 'void std::vector<_Tp, _Alloc>::pop_back() [with _Tp = std::tuple<long double, long long int, long long int>; _Alloc = std::allocator<std::tuple<long double, long long int, long long int> >]'
/usr/include/c++/11/bits/stl_queue.h:679:12:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::pop() [with _Tp = std::tuple<long double, long long int, long long int>; _Sequence = std::vector<std::tuple<long double, long long int, long long int> >; _Compare = std::greater<std::tuple<long double, long long int, long long int> >]'
cyberland.cpp:63:15:   required from here
/usr/include/c++/11/bits/stl_construct.h:88:22: error: invalid use of incomplete type 'class std::tuple<long double, long long int, long long int>'
   88 |         __location->~_Tp();
      |         ~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from cyberland.h:1,
                 from cyberland.cpp:1:
/usr/include/c++/11/type_traits:45:11: note: declaration of 'class std::tuple<long double, long long int, long long int>'
   45 |     class tuple;
      |           ^~~~~