| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 28860 | 2017-07-17T11:11:20 Z | nibnalin | Dreaming (IOI13_dreaming) | C++14 | Compilation error |
0 ms | 0 KB |
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include "dreaming.h"
using namespace std;
const int maxn = int(1e5)+5, inf = int(1e9)+5;
int n, m, l, D[2][maxn], vis[maxn];
vector<int> cur_comp;
vector<pair<int, int>> guys, graph[maxn];
int dfs(int node, int par, int d, int type)
{
D[type][node] = d;
if(type) cur_comp.push_back(node);
int cur = node;
for(auto it: graph[node])
{
if(it.first != par)
{
int tmp = dfs(it.first, node, d+it.second, type);
if(D[type][cur] < D[type][tmp]) cur = tmp;
}
}
return cur;
}
int travelTime(int _N, int _M, int _L, int _A[], int _B[], int _T[]) {
n = _N, m = _M, l = _L;
for(int i = 0;i < m;i++)
{
graph[_A[i]].push_back({_B[i], _T[i]});
graph[_B[i]].push_back({_A[i], _T[i]});
}
int res = -1;
set<pair<int, int>, greater<pair<int, int>>()> S;
for(int i = 0;i < n;i++)
{
if(!vis[i])
{
cur_comp.clear();
int f1 = dfs(i, -1, 0, 0);
int f2 = dfs(f1, -1, 0, 0);
dfs(f2, -1, 0, 1);
pair<int, int> mini = {inf, inf};
for(auto it: cur_comp)
{
mini = min(mini, {max(D[0][it], D[1][it]), it});
vis[it] = 1;
}
res = max(res, D[0][f2]);
//cout << mini.first << " " << mini.second << "\n";
guys.push_back(mini);
S.insert(mini);
}
}
int res2 = inf;
for(auto it: guys)
{
if(int(S.size()) < 2) continue;
S.erase(it), S.insert({it.first-l, it.second});
int tmp = l*2+((S.begin()->first)+(next(S.begin())->first));
res2 = min(res2, tmp);
S.insert(it), S.erase({it.first-l, it.second});
}
return max(res, res2);
}
Compilation message
In file included from /usr/include/c++/7/set:60:0,
from dreaming.cpp:4:
/usr/include/c++/7/bits/stl_tree.h: In instantiation of 'struct std::_Rb_tree_key_compare<std::greater<std::pair<int, int> >()>':
/usr/include/c++/7/bits/stl_tree.h:677:16: required from 'struct std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Rb_tree_impl<std::greater<std::pair<int, int> >(), false>'
/usr/include/c++/7/bits/stl_tree.h:708:31: required from 'class std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >'
/usr/include/c++/7/bits/stl_set.h:123:17: required from 'class std::set<std::pair<int, int>, std::greater<std::pair<int, int> >()>'
dreaming.cpp:40:49: required from here
/usr/include/c++/7/bits/stl_tree.h:144:21: error: field 'std::_Rb_tree_key_compare<std::greater<std::pair<int, int> >()>::_M_key_compare' invalidly declared function type
_Key_compare _M_key_compare;
^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h: In instantiation of 'class std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >':
/usr/include/c++/7/bits/stl_set.h:123:17: required from 'class std::set<std::pair<int, int>, std::greater<std::pair<int, int> >()>'
dreaming.cpp:40:49: required from here
/usr/include/c++/7/bits/stl_tree.h:956:7: error: function returning a function
key_comp() const
^~~~~~~~
In file included from /usr/include/c++/7/set:61:0,
from dreaming.cpp:4:
/usr/include/c++/7/bits/stl_set.h: In instantiation of 'class std::set<std::pair<int, int>, std::greater<std::pair<int, int> >()>':
dreaming.cpp:40:49: required from here
/usr/include/c++/7/bits/stl_set.h:317:7: error: function returning a function
key_comp() const
^~~~~~~~
/usr/include/c++/7/bits/stl_set.h:321:7: error: function returning a function
value_comp() const
^~~~~~~~~~
In file included from /usr/include/c++/7/set:60:0,
from dreaming.cpp:4:
/usr/include/c++/7/bits/stl_tree.h: In instantiation of '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 = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<int, int>]':
/usr/include/c++/7/bits/stl_tree.h:2091:28: 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 std::pair<int, int>&; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >]'
/usr/include/c++/7/bits/stl_set.h:501:48: required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<int, int>; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
dreaming.cpp:58:17: required from here
/usr/include/c++/7/bits/stl_tree.h:2038:11: error: too many arguments to function
__comp = _M_impl._M_key_compare(__k, _S_key(__x));
/usr/include/c++/7/bits/stl_tree.h:2038:11: error: cannot convert 'std::greater<std::pair<int, int> >' to 'bool' in assignment
/usr/include/c++/7/bits/stl_tree.h:2049:7: error: too many arguments to function
if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
^~
/usr/include/c++/7/bits/stl_tree.h:2049:19: error: could not convert '((std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >*)this)->std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_M_impl.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Rb_tree_impl<std::greater<std::pair<int, int> >(), false>::<anonymous>.std::_Rb_tree_key_compare<std::greater<std::pair<int, int> >()>::_M_key_compare()' from 'std::greater<std::pair<int, int> >' to 'bool'
if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, _Arg&&, _NodeGen&) [with _Arg = const std::pair<int, int>&; _NodeGen = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Alloc_node; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]':
/usr/include/c++/7/bits/stl_tree.h:2096:26: 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 std::pair<int, int>&; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >]'
/usr/include/c++/7/bits/stl_set.h:501:48: required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = std::pair<int, int>; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
dreaming.cpp:58:17: required from here
/usr/include/c++/7/bits/stl_tree.h:1750:10: error: too many arguments to function
bool __insert_left = (__x != 0 || __p == _M_end()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|| _M_impl._M_key_compare(_KeyOfValue()(__v),
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
_S_key(__p)));
~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1750:10: error: no match for 'operator||' (operand types are 'bool' and 'std::greater<std::pair<int, int> >')
/usr/include/c++/7/bits/stl_tree.h:1750:10: note: candidate: operator||(bool, bool) <built-in>
/usr/include/c++/7/bits/stl_tree.h:1750:10: note: no known conversion for argument 2 from 'std::greater<std::pair<int, int> >' to 'bool'
/usr/include/c++/7/bits/stl_tree.h: In instantiation of 'std::pair<std::_Rb_tree_iterator<_Val>, std::_Rb_tree_iterator<_Val> > std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::equal_range(const _Key&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >]':
/usr/include/c++/7/bits/stl_tree.h:2500:49: required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::erase(const _Key&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type = long unsigned int]'
/usr/include/c++/7/bits/stl_set.h:675:30: required from 'std::set<_Key, _Compare, _Alloc>::size_type std::set<_Key, _Compare, _Alloc>::erase(const key_type&) [with _Key = std::pair<int, int>; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::size_type = long unsigned int; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
dreaming.cpp:66:13: required from here
/usr/include/c++/7/bits/stl_tree.h:1940:4: error: too many arguments to function
if (_M_impl._M_key_compare(_S_key(__x), __k))
^~
/usr/include/c++/7/bits/stl_tree.h:1940:16: error: could not convert '((std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >*)this)->std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_M_impl.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Rb_tree_impl<std::greater<std::pair<int, int> >(), false>::<anonymous>.std::_Rb_tree_key_compare<std::greater<std::pair<int, int> >()>::_M_key_compare()' from 'std::greater<std::pair<int, int> >' to 'bool'
if (_M_impl._M_key_compare(_S_key(__x), __k))
~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1942:9: error: too many arguments to function
else if (_M_impl._M_key_compare(__k, _S_key(__x)))
^~
/usr/include/c++/7/bits/stl_tree.h:1942:21: error: could not convert '((std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >*)this)->std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_M_impl.std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Rb_tree_impl<std::greater<std::pair<int, int> >(), false>::<anonymous>.std::_Rb_tree_key_compare<std::greater<std::pair<int, int> >()>::_M_key_compare()' from 'std::greater<std::pair<int, int> >' to 'bool'
else if (_M_impl._M_key_compare(__k, _S_key(__x)))
~~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h: In instantiation of 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, _Arg&&, _NodeGen&) [with _Arg = std::pair<int, int>; _NodeGen = std::_Rb_tree<std::pair<int, int>, std::pair<int, int>, std::_Identity<std::pair<int, int> >, std::greater<std::pair<int, int> >(), std::allocator<std::pair<int, int> > >::_Alloc_node; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]':
/usr/include/c++/7/bits/stl_tree.h:2096:26: required from 'std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = std::pair<int, int>; _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >]'
/usr/include/c++/7/bits/stl_set.h:510:48: required from 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = std::pair<int, int>; _Compare = std::greater<std::pair<int, int> >(); _Alloc = std::allocator<std::pair<int, int> >; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::value_type = std::pair<int, int>]'
dreaming.cpp:66:48: required from here
/usr/include/c++/7/bits/stl_tree.h:1750:10: error: too many arguments to function
bool __insert_left = (__x != 0 || __p == _M_end()
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
|| _M_impl._M_key_compare(_KeyOfValue()(__v),
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
_S_key(__p)));
~~~~~~~~~~~~~
/usr/include/c++/7/bits/stl_tree.h:1750:10: error: no match for 'operator||' (operand types are 'bool' and 'std::greater<std::pair<int, int> >')
/usr/include/c++/7/bits/stl_tree.h:1750:10: note: candidate: operator||(bool, bool) <built-in>
/usr/include/c++/7/bits/stl_tree.h:1750:10: note: no known conversion for argument 2 from 'std::greater<std::pair<int, int> >' to 'bool'