Submission #298709

#	Time	Username	Problem	Language	Result	Execution time	Memory
298709		eohomegrownapps	Sky Walking (IOI19_walk)	C++14	Compilation error	0 ms	0 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

//vector<pair<int,int>> adjlist[10000000]; // weight, node
vector<pair<int,int>> adjlist;
ll INF = 1e18;

ll dijkstra(int n, int a, int b){
    vector<ll> distance(n);
    for (int i = 0; i<n; i++){
        distance[i]=INF;
    }
    distance[a]=0;
    //priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    //pq.push({0,a});
    set<pair<ll,int>> pq;
    pq.insert({0,a});
    while (pq.size()>0){
        auto f = *pq.begin();
        pq.erase(pq.begin());
        if (f.first>distance[f.second]){continue;}
        for (auto p : adjlist[f.second]){
            if (distance[f.second]+p.first<distance[p.second]){
                distance[p.second]=distance[f.second]+p.first;
                pq.insert({distance[p.second],p.second});
            }
        }
    }
    return (distance[b]==INF)?-1:distance[b];
}

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	// x - horizontal distance
    int n = x.size();
    vector<int> coords = x;
    sort(coords.begin(),coords.end());
    vector<int> heights(n);
    for (int i = 0; i<n; i++){
        heights[i]=h[lower_bound(coords.begin(),coords.end(),x[i])-coords.begin()];
    }
    int m = l.size();

    vector<int> inds(m);
    for (int i = 0; i<m; i++){
        inds[i]=i;
    }
    sort(inds.begin(),inds.end(),[y](int a, int b){return y[a]<y[b];});
    int numnodes = 0;
    vector<int> lastnode(n);
    vector<int> lastheight(n,0);
    adjlist.resize(n);
    for (int i = 0; i<n; i++){
        lastnode[i]=i;
    }

    set<int> hinds;
    vector<int> ind_order_height(n);
    for (int i = 0; i<n; i++){
        ind_order_height[i]=i;
        hinds.insert(i);
    }
    sort(ind_order_height.begin(),ind_order_height.end(),[heights](int a, int b){return heights[a]<heights[b];});

    int curnode = n;
    int ptr = 0;
    for (int i = 0; i<m; i++){
        while (ptr<n&&heights[ind_order_height[ptr]]<y[inds[i]]){
            hinds.erase(ind_order_height[ptr]);
            ptr++;
        }
        // process skywalk inds[i]
        int lc = l[inds[i]];
        int rc = r[inds[i]];
        //cout<<"process "<<lc<<' '<<rc<<'\n';
        int prev = -1;
        auto it = hinds.lower_bound(lc);
        int lv = *it;
        while (it!=hinds.end()&&(*it)<=rc){
            int j = *it;
            //cout<<"heights: "<<heights[j]<<'\n';
            // link j to below
            
            if (heights[j]<y[inds[i]]){assert(1==0);}
            if (lastheight[j]!=y[inds[i]]){
                //cout<<"connect "<<curnode<<' '<<lastnode[j]<<'\n';
                adjlist.push_back(vector<pair<ll,int>>());
                adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
                adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
                lastnode[j]=curnode;
                lastheight[j]=y[inds[i]];
                curnode++;
            }
            // link j to left
            if (j!=lv){
                //cout<<"connect "<<lastnode[j]<<' '<<lastnode[prev]<<'\n';
                adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
                adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
            }
            prev = j;
            it++;
        }
        //cout<<"bleh"<<endl;
    }
    return dijkstra(curnode,s,g);
}

Compilation message (stderr)

walk.cpp: In function 'll dijkstra(int, int, int)':
walk.cpp:25:39: error: no matching function for call to 'begin(std::pair<int, int>&)'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/c++/9/bits/stl_vector.h:63,
                 from /usr/include/c++/9/vector:67,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/9/initializer_list:89:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   89 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/9/initializer_list:89:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/c++/9/vector:69,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/9/bits/range_access.h:48:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&)'
   48 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:48:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::pair<int, int>]':
walk.cpp:25:39:   required from here
/usr/include/c++/9/bits/range_access.h:48:50: error: 'struct std::pair<int, int>' has no member named 'begin'
   48 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |                                           ~~~~~~~^~~~~
/usr/include/c++/9/bits/range_access.h:58:5: note: candidate: 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&)'
   58 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:58:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<int, int>]':
walk.cpp:25:39:   required from here
/usr/include/c++/9/bits/range_access.h:58:56: error: 'const struct std::pair<int, int>' has no member named 'begin'
   58 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |                                                 ~~~~~~~^~~~~
/usr/include/c++/9/bits/range_access.h:87:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   87 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/9/bits/range_access.h:87:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   mismatched types '_Tp [_Nm]' and 'std::pair<int, int>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from walk.cpp:2:
/usr/include/c++/9/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/9/valarray:1214:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'std::valarray<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from walk.cpp:2:
/usr/include/c++/9/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/9/valarray:1224:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
walk.cpp:25:39: error: no matching function for call to 'end(std::pair<int, int>&)'
In file included from /usr/include/c++/9/bits/stl_vector.h:63,
                 from /usr/include/c++/9/vector:67,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/9/initializer_list:99:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
   99 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/9/initializer_list:99:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'std::initializer_list<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/c++/9/vector:69,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/9/bits/range_access.h:68:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(_Container&)'
   68 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/9/bits/range_access.h:68:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(_Container&) [with _Container = std::pair<int, int>]':
walk.cpp:25:39:   required from here
/usr/include/c++/9/bits/range_access.h:68:48: error: 'struct std::pair<int, int>' has no member named 'end'
   68 |     end(_Container& __cont) -> decltype(__cont.end())
      |                                         ~~~~~~~^~~
/usr/include/c++/9/bits/range_access.h:78:5: note: candidate: 'template<class _Container> decltype (__cont.end()) std::end(const _Container&)'
   78 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/9/bits/range_access.h:78:5: note:   template argument deduction/substitution failed:
/usr/include/c++/9/bits/range_access.h: In substitution of 'template<class _Container> decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<int, int>]':
walk.cpp:25:39:   required from here
/usr/include/c++/9/bits/range_access.h:78:54: error: 'const struct std::pair<int, int>' has no member named 'end'
   78 |     end(const _Container& __cont) -> decltype(__cont.end())
      |                                               ~~~~~~~^~~
/usr/include/c++/9/bits/range_access.h:97:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
   97 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/9/bits/range_access.h:97:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   mismatched types '_Tp [_Nm]' and 'std::pair<int, int>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from walk.cpp:2:
/usr/include/c++/9/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/9/valarray:1234:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'std::valarray<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:95,
                 from walk.cpp:2:
/usr/include/c++/9/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/9/valarray:1244:5: note:   template argument deduction/substitution failed:
walk.cpp:25:39: note:   'std::pair<int, int>' is not derived from 'const std::valarray<_Tp>'
   25 |         for (auto p : adjlist[f.second]){
      |                                       ^
walk.cpp:28:56: error: no matching function for call to 'std::set<std::pair<long long int, int> >::insert(<brace-enclosed initializer list>)'
   28 |                 pq.insert({distance[p.second],p.second});
      |                                                        ^
In file included from /usr/include/c++/9/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from walk.cpp:2:
/usr/include/c++/9/bits/stl_set.h:509:7: note: candidate: '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>::insert(const value_type&) [with _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long 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_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, int>]'
  509 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_set.h:509:32: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<long long int, int>&'}
  509 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_set.h:518:7: note: candidate: '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>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long 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_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, int>]'
  518 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_set.h:518:27: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::set<std::pair<long long int, int> >::value_type&&' {aka 'std::pair<long long int, int>&&'}
  518 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_set.h:546:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, int>]'
  546 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_set.h:546:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_set.h:551:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree_const_iterator<std::pair<long long int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<long long int, int>]'
  551 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_set.h:551:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/9/bits/stl_set.h:566:2: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long int, int> >]'
  566 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/9/bits/stl_set.h:566:2: note:   template argument deduction/substitution failed:
walk.cpp:28:56: note:   candidate expects 2 arguments, 1 provided
   28 |                 pq.insert({distance[p.second],p.second});
      |                                                        ^
In file included from /usr/include/c++/9/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:87,
                 from walk.cpp:2:
/usr/include/c++/9/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = std::pair<long long int, int>; _Compare = std::less<std::pair<long long int, int> >; _Alloc = std::allocator<std::pair<long long int, int> >]'
  578 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/9/bits/stl_set.h:578:43: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::initializer_list<std::pair<long long int, int> >'
  578 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:89:57: error: no matching function for call to 'std::vector<std::pair<int, int> >::push_back(std::vector<std::pair<long long int, int> >)'
   89 |                 adjlist.push_back(vector<pair<ll,int>>());
      |                                                         ^
In file included from /usr/include/c++/9/vector:67,
                 from walk.h:4,
                 from walk.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:1184:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1184 |       push_back(const value_type& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1184:35: note:   no known conversion for argument 1 from 'std::vector<std::pair<long long int, int> >' to 'const value_type&' {aka 'const std::pair<int, int>&'}
 1184 |       push_back(const value_type& __x)
      |                 ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/9/bits/stl_vector.h:1200:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, int>]'
 1200 |       push_back(value_type&& __x)
      |       ^~~~~~~~~
/usr/include/c++/9/bits/stl_vector.h:1200:30: note:   no known conversion for argument 1 from 'std::vector<std::pair<long long int, int> >' to 'std::vector<std::pair<int, int> >::value_type&&' {aka 'std::pair<int, int>&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
walk.cpp:90:34: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'push_back'
   90 |                 adjlist[curnode].push_back({y[inds[i]]-lastheight[j],lastnode[j]});
      |                                  ^~~~~~~~~
walk.cpp:91:38: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'push_back'
   91 |                 adjlist[lastnode[j]].push_back({y[inds[i]]-lastheight[j],curnode});
      |                                      ^~~~~~~~~
walk.cpp:99:38: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'push_back'
   99 |                 adjlist[lastnode[j]].push_back({x[j]-x[prev],lastnode[prev]});
      |                                      ^~~~~~~~~
walk.cpp:100:41: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<int, int> >, std::pair<int, int> >::value_type' {aka 'struct std::pair<int, int>'} has no member named 'push_back'
  100 |                 adjlist[lastnode[prev]].push_back({x[j]-x[prev],lastnode[j]});
      |                                         ^~~~~~~~~
walk.cpp:51:9: warning: unused variable 'numnodes' [-Wunused-variable]
   51 |     int numnodes = 0;
      |         ^~~~~~~~