Submission #292534

#	Time	Username	Problem	Language	Result	Execution time	Memory
292534		Saboon	Roller Coaster Railroad (IOI16_railroad)	C++17	Compilation error	0 ms	0 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
const int inf = 1e9;

int n;
int par[2*maxn], degIn[2*maxn], degOut[2*maxn];

int get_par(int v){
    return par[v] < 0 ? v : par[v] = get_par(par[v]);
}

bool merge(int v, int u){
    if (get_par(v) == get_par(u))
        return false;
    par[v] = u;
    return true;
}

ll plan_roller_coaster(vector<int> s, vector<int> t){
    s.push_back(inf);
    t.push_back(1);
    n = s.size();
    vector<int> Cmp;
    for (auto it : s) Cmp.push_back(it);
    for (auto it : t) Cmp.push_back(it);
    sort(Cmp.begin(), Cmp.end());
    Cmp.resize(unique(Cmp.begin(), Cmp.end())-Cmp.begin());
    memset(par, -1, sizeof par);
    for (int i = 0; i < n; i++){
        s[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
        t[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
        merge(t[i],s[i]);
        degOut[s[i]] ++, degIn[t[i]] ++;
    }
    int m = Cmp.size();
    ll untilNow = 0;
    for (int i = 0; i < m-1; i++){
        int diff = abs(degIn[i]-degOut[i]);
        if (diff > 0)
            merge(i,i+1);
        if (degIn[i] < degOut[i]){
            degIn[i] += diff;
            degOut[i+1] += diff;
            untilNow += 1LL*degIn[i]-degOut[i]*(Cmp[i+1]-Cmp[i]);
        }
        else{
            degOut[i] += diff;
            degIn[i+1] += diff;
        }
    }
    vector<pair<int,pair<int,int>>> E;
    for (int i = 0; i < m-1; i++)
        if (get_par(i) != get_par(i+1))
            E.push_back({cmp[i+1]-cmp[i],{get_par(i),get_par(i+1)}})
    sort(E.begin(),E.end());
    for (auto it : E){
        int v = E.second.first, u = E.second.second;
        if (merge(v,u))
            untilNow += E.first;
    }
    return untilNow;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:34:50: error: no matching function for call to 'lower_bound(std::vector<int>::iterator, std::vector<int>::iterator)'
   34 |         s[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
In file included from /usr/include/c++/9/vector:60,
                 from railroad.h:3,
                 from railroad.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:1004:5: note: candidate: 'template<class _ForwardIterator, class _Tp> _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1004 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_algobase.h:1004:5: note:   template argument deduction/substitution failed:
railroad.cpp:34:50: note:   candidate expects 3 arguments, 2 provided
   34 |         s[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from railroad.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:2022:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
 2022 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_algo.h:2022:5: note:   template argument deduction/substitution failed:
railroad.cpp:34:50: note:   candidate expects 4 arguments, 2 provided
   34 |         s[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
railroad.cpp:35:50: error: no matching function for call to 'lower_bound(std::vector<int>::iterator, std::vector<int>::iterator)'
   35 |         t[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
In file included from /usr/include/c++/9/vector:60,
                 from railroad.h:3,
                 from railroad.cpp:1:
/usr/include/c++/9/bits/stl_algobase.h:1004:5: note: candidate: 'template<class _ForwardIterator, class _Tp> _ForwardIterator std::lower_bound(_ForwardIterator, _ForwardIterator, const _Tp&)'
 1004 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_algobase.h:1004:5: note:   template argument deduction/substitution failed:
railroad.cpp:35:50: note:   candidate expects 3 arguments, 2 provided
   35 |         t[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from railroad.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:2022:5: note: candidate: 'template<class _FIter, class _Tp, class _Compare> _FIter std::lower_bound(_FIter, _FIter, const _Tp&, _Compare)'
 2022 |     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
      |     ^~~~~~~~~~~
/usr/include/c++/9/bits/stl_algo.h:2022:5: note:   template argument deduction/substitution failed:
railroad.cpp:35:50: note:   candidate expects 4 arguments, 2 provided
   35 |         t[i] = lower_bound(Cmp.begin(), Cmp.end()) - Cmp.begin();
      |                                                  ^
railroad.cpp:58:26: error: 'cmp' was not declared in this scope; did you mean 'Cmp'?
   58 |             E.push_back({cmp[i+1]-cmp[i],{get_par(i),get_par(i+1)}})
      |                          ^~~
      |                          Cmp
railroad.cpp:58:68: error: no matching function for call to 'std::vector<std::pair<int, std::pair<int, int> > >::push_back(<brace-enclosed initializer list>)'
   58 |             E.push_back({cmp[i+1]-cmp[i],{get_par(i),get_par(i+1)}})
      |                                                                    ^
In file included from /usr/include/c++/9/vector:67,
                 from railroad.h:3,
                 from railroad.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, std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, std::pair<int, int> > >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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 '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, 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, std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, std::pair<int, int> > >; std::vector<_Tp, _Alloc>::value_type = std::pair<int, 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 '<brace-enclosed initializer list>' to 'std::vector<std::pair<int, std::pair<int, int> > >::value_type&&' {aka 'std::pair<int, std::pair<int, int> >&&'}
 1200 |       push_back(value_type&& __x)
      |                 ~~~~~~~~~~~~~^~~
railroad.cpp:61:19: error: 'class std::vector<std::pair<int, std::pair<int, int> > >' has no member named 'second'
   61 |         int v = E.second.first, u = E.second.second;
      |                   ^~~~~~
railroad.cpp:62:21: error: 'u' was not declared in this scope
   62 |         if (merge(v,u))
      |                     ^
railroad.cpp:63:27: error: 'class std::vector<std::pair<int, std::pair<int, int> > >' has no member named 'first'
   63 |             untilNow += E.first;
      |                           ^~~~~