Submission #253105

#	Time	Username	Problem	Language	Result	Execution time	Memory
253105		Hehehe	Roller Coaster Railroad (IOI16_railroad)	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.

railroad

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "railroad.h"

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 7;
const int H = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

ll n, m, p[H], siz[H];
ll pref[H];

struct edge{
    ll ff, ss, w;
};

int find_set(int x){
    if(x == p[x])return x;
    return p[x] = find_set(p[x]);
}

void unionn(int x, int y){

    x = find_set(x);
    y = find_set(y);

    if(x == y)return;

    if(siz[x] < siz[y])swap(x, y);

    p[y] = x;
    siz[x] += siz[y];
}

long long plan_roller_coaster(vector<int> s, vector<int> t) {

    n = (ll)sz(s);
    ll ans = 0;

    vector<ll>v;

    for(int i = 0; i < n; i++){
        v.push_back(s[i]);
        v.push_back(t[i]);
    }

    sort(all(v));
    v.resize(unique(all(v))-v.begin());

    m = sz(v);

    for(int i = 0; i <= m; i++){
        p[i] = i;
        pref[i] = 0;
        siz[i] = 1;
    }

    pref[1] = -1;
    for(int i = 0; i < n; i++){
        s[i] = lower_bound(all(v), s[i]) - v.begin();
        t[i] = lower_bound(all(v), t[i]) - v.begin();

        pref[s[i]]++;
        pref[t[i]]--;

        unionn(s[i], t[i]);
    }

    vector<edge>edges;

    for(int i = 0; i < m - 1; i++){

        pref[i] += (i == 0 ? 0 : pref[i - 1]);

        if(pref[i] != 0){
            ans += max(0ll, pref[i])*(v[i + 1] - v[i]);
            unionn(i, i + 1);
        }

        edges.push_back({i, i + 1, v[i + 1] - v[i]});
    }
    
    sort(all(edges), [](ll l, ll r){
         return (l.w < r.w);
    });

    for(auto it : edges){
        if(find_set(it.ff) == find_set(it.ss))continue;

        ans += it.w;
        unionn(it.ff, it.ss);
    }

    return ans;
}

Compilation message (stderr)

railroad.cpp: In lambda function:
railroad.cpp:99:20: error: request for member 'w' in 'l', which is of non-class type 'll {aka long long int}'
          return (l.w < r.w);
                    ^
railroad.cpp:99:26: error: request for member 'w' in 'r', which is of non-class type 'll {aka long long int}'
          return (l.w < r.w);
                          ^
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Iterator2 = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]':
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]'
railroad.cpp:100:6:   required from here
/usr/include/c++/7/bits/predefined_ops.h:143:18: error: no match for call to '(plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>) (edge&, edge&)'
         { return bool(_M_comp(*__it1, *__it2)); }
                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:143:18: note: candidate: void (*)(ll, ll) {aka void (*)(long long int, long long int)} <conversion>
/usr/include/c++/7/bits/predefined_ops.h:143:18: note:   candidate expects 3 arguments, 3 provided
railroad.cpp:98:35: note: candidate: plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>
     sort(all(edges), [](ll l, ll r){
                                   ^
railroad.cpp:98:35: note:   no known conversion for argument 1 from 'edge' to 'll {aka long long int}'
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = edge; _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]':
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]'
railroad.cpp:100:6:   required from here
/usr/include/c++/7/bits/predefined_ops.h:215:11: error: no match for call to '(plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>) (edge&, edge&)'
  { return bool(_M_comp(__val, *__it)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:215:11: note: candidate: void (*)(ll, ll) {aka void (*)(long long int, long long int)} <conversion>
/usr/include/c++/7/bits/predefined_ops.h:215:11: note:   candidate expects 3 arguments, 3 provided
railroad.cpp:98:35: note: candidate: plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>
     sort(all(edges), [](ll l, ll r){
                                   ^
railroad.cpp:98:35: note:   no known conversion for argument 1 from 'edge' to 'll {aka long long int}'
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 railroad.cpp:1:
/usr/include/c++/7/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Value = edge; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]':
/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_comp_val<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/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_comp_iter<plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)> >]'
/usr/include/c++/7/bits/stl_algo.h:4868:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<edge*, std::vector<edge> >; _Compare = plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>]'
railroad.cpp:100:6:   required from here
/usr/include/c++/7/bits/predefined_ops.h:177:11: error: no match for call to '(plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>) (edge&, edge&)'
  { return bool(_M_comp(*__it, __val)); }
           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/predefined_ops.h:177:11: note: candidate: void (*)(ll, ll) {aka void (*)(long long int, long long int)} <conversion>
/usr/include/c++/7/bits/predefined_ops.h:177:11: note:   candidate expects 3 arguments, 3 provided
railroad.cpp:98:35: note: candidate: plan_roller_coaster(std::vector<int>, std::vector<int>)::<lambda(ll, ll)>
     sort(all(edges), [](ll l, ll r){
                                   ^
railroad.cpp:98:35: note:   no known conversion for argument 1 from 'edge' to 'll {aka long long int}'