| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1318213 | Johan | Dreaming (IOI13_dreaming) | C++20 | Compilation error | 0 ms | 0 KiB |
#include "dreaming.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
int pa[N];
vector < int > adj[N];
map < int , int > dist;
map < pair < int , int > , int > we;
vector < int > par(N, -1);
int find(int u){
if(par[u] < 0)return u;
else return par[u] = find(par[u]);
}
void uni(int u, int v){
u = find(u);
v = find(v);
if(u == v)return;
par[u] += par[v];
par[v] = u;
}
void dfs(int u, int p = -1){
for(auto v : adj[u]){
if(v != p){
dist[v] = dist[u] + we[{u, v}];
dfs(v, u);
}
}
}
void dfs_(int u, int end, int p = -1){
pa[u] = p;
for(auto v : adj[u]){
if(v != p)
dfs_(v, end, u);
}
}
array < int , 3 > centre(int st, int end){
int sz = 0;
vector < int > path = {end};
while(end != st){
sz += we[{end, pa[end]}];
end = pa[end];
path.push_back(end);
}
int mn = sz, diametr = sz, cur = 0, node = path[0], far;
for(int i = 1; i < path.size(); i++){
int W = we[{path[i], path[i - 1]}];
sz -= W;
cur += W;
if(mn > max(sz, cur)){
if(sz > cur)far = path.back();
else far = path[0];
mn = max(sz, cur);
node = path[i];
}
}
return {diametr, node, mn};
}
int travelTime(int n, int m, int L, int u[], int v[], int w[]){
for(int i = 0; i < m; i++){
we[{u[i], v[i]}] = w[i];
we[{v[i], u[i]}] = w[i];
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
uni(u[i], v[i]);
}
set < int > cmps;
for(int i = 0; i < n; i++)
cmps.insert(find(i));
vector < array < int , 3 > > x;
for(auto nd : cmps){
dfs(nd);
int mx = 0, u = nd, v = nd;
for(auto e : dist){
int node = e.first;
int dis = e.second;
if(dis > mx){
mx = dis;
u = node;
}
}
mx = 0;
dist.clear();
dfs(u);
for(auto e : dist){
int node = e.first;
int dis = e.second;
if(dis > mx){
mx = dis;
v = node;
}
}
dist.clear();
dfs_(u, v);
x.push_back(centre(u, v));
}
sort(x.rbegin(), x.rend());
int Node = x[0][1], diss = x[0][2];
for(int i = 1; i < x.size(); i++){
adj[Node].push_back(x[i][1]);
adj[x[i][1]].push_back(Node);
we[{Node, x[i][1]}] = L;
we[{x[i][1], Node}] = L;
int mx = max(x[0][0], x[i][0]);
mx = max(mx, L + diss + x[i][2]);
diss = max(diss, L + x[i] + 2);
x[0][0] = mx;
}
return x[0][0];
}
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:105:36: error: no match for 'operator+' (operand types are 'int' and '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'})
105 | diss = max(diss, L + x[i] + 2);
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from dreaming.cpp:2:
/usr/include/c++/13/bits/stl_iterator.h:634:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_IteratorL> std::operator+(typename reverse_iterator<_IteratorL>::difference_type, const reverse_iterator<_IteratorL>&)'
634 | operator+(typename reverse_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:634:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::reverse_iterator<_IteratorL>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/stl_iterator.h:1808:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename move_iterator<_IteratorL>::difference_type, const move_iterator<_IteratorL>&)'
1808 | operator+(typename move_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1808:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::move_iterator<_IteratorL>'
105 | diss = max(diss, L + x[i] + 2);
| ^
In file included from /usr/include/c++/13/string:54,
from /usr/include/c++/13/bitset:52,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52:
/usr/include/c++/13/bits/basic_string.h:3553:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3553 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3553:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3571:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3571 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3571:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const _CharT*' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3590:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3590 | operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs)
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3590:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3607:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
3607 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3607:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3625:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, _CharT)'
3625 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3625:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3637:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const __cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
3637 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3637:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3644:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const __cxx11::basic_string<_CharT, _Traits, _Allocator>&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3644 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3644:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3651:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3651 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3651:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3674:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const _CharT*, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3674 | operator+(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3674:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const _CharT*' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3681:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(_CharT, __cxx11::basic_string<_CharT, _Traits, _Allocator>&&)'
3681 | operator+(_CharT __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3681:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3688:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, const _CharT*)'
3688 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3688:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/basic_string.h:3695:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> constexpr std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(__cxx11::basic_string<_CharT, _Traits, _Allocator>&&, _CharT)'
3695 | operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
| ^~~~~~~~
/usr/include/c++/13/bits/basic_string.h:3695:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'std::__cxx11::basic_string<_CharT, _Traits, _Allocator>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
In file included from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:335:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&, const complex<_Tp>&)'
335 | operator+(const complex<_Tp>& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:335:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::complex<_Tp>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/complex:344:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&, const _Tp&)'
344 | operator+(const complex<_Tp>& __x, const _Tp& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:344:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::complex<_Tp>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/complex:353:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const _Tp&, const complex<_Tp>&)'
353 | operator+(const _Tp& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:353:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::complex<_Tp>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/complex:454:5: note: candidate: 'template<class _Tp> constexpr std::complex<_Tp> std::operator+(const complex<_Tp>&)'
454 | operator+(const complex<_Tp>& __x)
| ^~~~~~~~
/usr/include/c++/13/complex:454:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::complex<_Tp>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
In file included from /usr/include/c++/13/valarray:605,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const typename _Dom::value_type&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const _Expr<_Dom1, typename _Dom1::value_type>&, const valarray<typename _Dom::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/bits/valarray_after.h:405:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__plus, typename _Dom1::value_type>::result_type> std::operator+(const valarray<typename _Dom::value_type>&, const _Expr<_Dom1, typename _Dom1::value_type>&)'
405 | _DEFINE_EXPR_BINARY_OPERATOR(+, struct std::__plus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:405:5: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const valarray<_Tp>&, const valarray<_Tp>&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::valarray<_Tp>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const valarray<_Tp>&, const typename valarray<_Tp>::value_type&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: mismatched types 'const std::valarray<_Tp>' and 'int'
105 | diss = max(diss, L + x[i] + 2);
| ^
/usr/include/c++/13/valarray:1196:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__plus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__plus, _Tp>::result_type> std::operator+(const typename valarray<_Tp>::value_type&, const valarray<_Tp>&)'
1196 | _DEFINE_BINARY_OPERATOR(+, __plus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/valarray:1196:1: note: template argument deduction/substitution failed:
dreaming.cpp:105:41: note: '__gnu_cxx::__alloc_traits<std::allocator<std::array<int, 3> >, std::array<int, 3> >::value_type' {aka 'std::array<int, 3>'} is not derived from 'const std::valarray<_Tp>'
105 | diss = max(diss, L + x[i] + 2);
| ^