Submission #335197

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335197	2020-12-11T12:23:30 Z	blue	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KB

dreaming

#include "dreaming.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;

vector<int> edge[100001];
vector<int> weight[100001];
vector<int> maxdist(100001, 0);
vector<int> children(100001, 0);
vector<int> visit(100001, 0);
vector<int> roots;

struct distcomp
{
    bool operator () (int a, int b)
    {
        if(maxdist[a] == maxdist[b]) return a < b;
        return maxdist[a] < maxdist[b];
    }
};

int travelTime(int N, int M, int L, int A[], int B[], int T[])
//number of nodes, number of edges, common length, edge A[i]-A[i] with length T[i]
{
    for(int i = 0; i < M; i++)
    {
        edge[A[i]].push_back(B[i]);
        weight[A[i]].push_back(T[i]);
        edge[B[i]].push_back(A[i]);
        weight[B[i]].push_back(T[i]);
    }

    set<int, distcomp> tbv;
    for(int i = 0; i < N; i++)
    {
        if(edge[i].size() == 0) roots.push_back(0);
        if(edge[i].size() == 1) tbv.insert(i);
    }

    int u, v, w;
    while(!tbv.empty())
    {
        u = *tbv.begin();
        tbv.erase(tbv.begin());
        visit[u] = 1;

        for(int i = 0; i < edge[u].size(); i++)
        {
            v = edge[u][i];
            w = weight[u][i];

            if(!visit[v])
            {
                children[v]++;
                maxdist[v] = max(maxdist[v], maxdist[u] + w);
                if(children[v] == edge[v].size() - 1) tbv.insert(v);
            }
            else
            {
                maxdist[u] = max(maxdist[u], maxdist[v] + w);
            }
        }
        if(edge[u].size() == children[u]) roots.push_back(maxdist[u]);
    }
    if(M == N-1) return roots[0];
    else
    {
        sort(roots.begin(), roots.end());
        return roots[roots.size() - 2] + L + roots[roots.size() - 1];
    }
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:50:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for(int i = 0; i < edge[u].size(); i++)
      |                        ~~^~~~~~~~~~~~~~~~
dreaming.cpp:59:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                 if(children[v] == edge[v].size() - 1) tbv.insert(v);
dreaming.cpp:66:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   66 |         if(edge[u].size() == children[u]) roots.push_back(maxdist[u]);
In file included from /usr/include/c++/9/set:60,
                 from dreaming.cpp:4:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = distcomp; _Alloc = std::allocator<int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<int>*]':
/usr/include/c++/9/bits/stl_tree.h:2095:47:   required from 'std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = distcomp; _Alloc = std::allocator<int>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = int]'
/usr/include/c++/9/bits/stl_tree.h:2148:4:   required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = const int&; _Key = int; _Val = int; _KeyOfValue = std::_Identity<int>; _Compare = distcomp; _Alloc = std::allocator<int>]'
/usr/include/c++/9/bits/stl_set.h:511:48:   required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = distcomp; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<int>; std::set<_Key, _Compare, _Alloc>::value_type = int]'
dreaming.cpp:40:45:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~