제출 #1331435

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1331435		Mamikonm1	악어의 지하 도시 (IOI11_crocodile)	C++17	컴파일 에러	0 ms	0 KiB

crocodile

#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
const int n=1e5+5;
const ll inf=1e18;
struct cost{
    ll mn1,mn2;
    cost(ll a=inf,ll b=inf){
        mn1=a;
        mn2=b;
    }
    void add(ll x){
        if(mn1>=x){
            mn2=mn1;
            mn1=x;
        }
        else if(mn2>=x)mn2=x;
    }
    bool operator<(cost&b){
        if(mn2==b.mn2)return mn1<b.mn1;
        return mn2<b.mn2;
    }
};
vector<cost>dp(n);
vector<pair<int,int>>graph[n];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    int u,v;
    for(int i=0;i<M;++i){
        u=R[i][0];v=R[i][1];
        graph[u].push_back({v,L[i]});
        graph[v].push_back({u,L[i]});
    }
    priority_queue<pair<cost,int>,vector<pair<cost,int>>,greater<>>q;
    for(int i=0;i<K;++i){
        u=P[i];
        dp[u]={0,0};
        q.push({dp[u],u});
    }
    bool vis[n+1];
    ll w;
    while(!q.empty()){
        u=q.top().second;
        w=q.top().first.mn2;
        q.pop();
        if(w!=dp[u].mn2)continue;
        for(auto&i:graph[u]){
            v=i.first;
            cost cur=dp[v];
            cur.add(i.second+w);
            if(cur<dp[v]){
                dp[v]=cur;
                q.push({dp[v],v});
            }
        }
    }
    return dp[0].mn2;
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from crocodile.cpp:1:
/usr/include/c++/13/bits/stl_pair.h: In instantiation of 'constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&) [with _T1 = cost; _T2 = int]':
/usr/include/c++/13/bits/stl_pair.h:849:18:   required from 'constexpr bool std::operator>(const pair<_T1, _T2>&, const pair<_T1, _T2>&) [with _T1 = cost; _T2 = int]'
/usr/include/c++/13/bits/stl_function.h:546:34:   required from 'static constexpr decltype(auto) std::greater<void>::_S_cmp(_Tp&&, _Up&&, std::false_type) [with _Tp = std::pair<cost, int>&; _Up = std::pair<cost, int>&; std::false_type = std::integral_constant<bool, false>]'
/usr/include/c++/13/bits/stl_function.h:531:17:   required from 'constexpr decltype ((forward<_Tp>(__t) > forward<_Up>(__u))) std::greater<void>::operator()(_Tp&&, _Up&&) const [with _Tp = std::pair<cost, int>&; _Up = std::pair<cost, int>&; decltype ((forward<_Tp>(__t) > forward<_Up>(__u))) = bool]'
/usr/include/c++/13/bits/predefined_ops.h:196:23:   required from 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<cost, int>*, std::vector<std::pair<cost, int> > >; _Value = std::pair<cost, int>; _Compare = std::greater<void>]'
/usr/include/c++/13/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<cost, int>*, vector<pair<cost, int> > >; _Distance = long int; _Tp = pair<cost, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<void> >]'
/usr/include/c++/13/bits/stl_heap.h:216:23:   required from 'void std::push_heap(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<cost, int>*, vector<pair<cost, int> > >; _Compare = greater<void>]'
/usr/include/c++/13/bits/stl_queue.h:749:16:   required from 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(value_type&&) [with _Tp = std::pair<cost, int>; _Sequence = std::vector<std::pair<cost, int> >; _Compare = std::greater<void>; value_type = std::pair<cost, int>]'
crocodile.cpp:39:15:   required from here
/usr/include/c++/13/bits/stl_pair.h:836:24: error: no match for 'operator<' (operand types are 'const cost' and 'const cost')
  836 |     { return __x.first < __y.first
      |              ~~~~~~~~~~^~~~~~~~~~~
crocodile.cpp:20:10: note: candidate: 'bool cost::operator<(cost&)' (near match)
   20 |     bool operator<(cost&b){
      |          ^~~~~~~~
crocodile.cpp:20:10: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/13/bits/stl_pair.h:836:30: error: binding reference of type 'cost&' to 'const cost' discards qualifiers
  836 |     { return __x.first < __y.first
      |                          ~~~~^~~~~
/usr/include/c++/13/bits/stl_pair.h:835:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
  835 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:835:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_pair.h:836:24: note:   'const cost' is not derived from 'const std::pair<_T1, _T2>'
  836 |     { return __x.first < __y.first
      |              ~~~~~~~~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:837:30: error: no match for 'operator<' (operand types are 'const cost' and 'const cost')
  837 |              || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                   ~~~~~~~~~~~^~~~~~~~~~~~
crocodile.cpp:20:10: note: candidate: 'bool cost::operator<(cost&)' (near match)
   20 |     bool operator<(cost&b){
      |          ^~~~~~~~
crocodile.cpp:20:10: note:   conversion of argument 1 would be ill-formed:
/usr/include/c++/13/bits/stl_pair.h:837:36: error: binding reference of type 'cost&' to 'const cost' discards qualifiers
  837 |              || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                                ~~~~^~~~~
/usr/include/c++/13/bits/stl_pair.h:835:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator<(const pair<_T1, _T2>&, const pair<_T1, _T2>&)'
  835 |     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_pair.h:835:5: note:   template argument deduction/substitution failed:
/usr/include/c++/13/bits/stl_pair.h:837:30: note:   'const cost' is not derived from 'const std::pair<_T1, _T2>'
  837 |              || (!(__y.first < __x.first) && __x.second < __y.second); }
      |                   ~~~~~~~~~~~^~~~~~~~~~~~