| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 416137 | 2021-06-02T05:10:54 Z | DEQK | Dreaming (IOI13_dreaming) | C++17 | Compilation error |
0 ms | 0 KB |
#include "dreaming.h"
#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N = 100100;
/*int travelTime(int n,int m,int l,vector<int> a,vector<int> b,vector<int> t) {
}*/
int n, m, l, ans;
int us[N], dp[N], was[N];
vector<pair<int, int>> g[N];
pair<int, int> best;
void dfs(int u) {
us[u] = 1;
for(auto to : g[u]) if(!us[to.first]) {
dfs(to.first);
dp[u] = max(dp[u], dp[to.first] + to.second);
}
}
void dfs2(int u,int val) {
was[u] = 1;
vector<int> p, s;
ans = max(ans, max(dp[u], val));
if(best.first > max(dp[u], val)) {
best = {max(dp[u], val), u};
}
for(int i = 0; i < g[u].size(); ++i) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
p.push_back(!p.empty() ? max(p.back(), dp[to] + c) : dp[to] + c);
}
for(int i = g[u].size() - 1; i >= 0; i--) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
s.push_back(s.empty() ? dp[to] + c : max(s.back(), dp[to] + c));
}
reverse(s.begin(), s.end());
int p = 0;
for(int i = 0; i < g[u].size(); i++) {
int to = g[u][i].first, c = g[u][i].second;
if(was[to]) continue;
int f = val;
++p;
if(p) f = max(f, p[p - 1]);
if(p + 1 < s.size()) f = max(f, s[p + 1]);
dfs2(to, f + c);
}
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
for(int i = 0; i < m; ++i) {
int u = a[i],v = b[i],w = t[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
vector<pair<int, int>> d;
for(int i = 0; i < n; ++i) {
if(!us[i]) {
dfs(i);
best = {1e18, 0};
dfs2(i, 0);
d.push_back(best);
}
}
sort(d.begin(), d.end(), [&] (pair<int, int> &x, pair<int, int> &y) {
return x.first > y.first;
});
if(d.size() > 1) {
ans = max(ans, d[0].first + d[1].first + l);
}
if(d.size() > 2) {
ans = max(ans, d[1].first + d[2].first + 2 * l);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs2(long long int, long long int)':
dreaming.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i = 0; i < g[u].size(); ++i) {
| ~~^~~~~~~~~~~~~
dreaming.cpp:40:6: error: conflicting declaration 'long long int p'
40 | int p = 0;
| ^
dreaming.cpp:24:14: note: previous declaration as 'std::vector<long long int> p'
24 | vector<int> p, s;
| ^
dreaming.cpp:41:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < g[u].size(); i++) {
| ~~^~~~~~~~~~~~~
dreaming.cpp:45:3: error: no match for 'operator++' (operand type is 'std::vector<long long int>')
45 | ++p;
| ^~~
dreaming.cpp:46:6: error: could not convert 'p' from 'std::vector<long long int>' to 'bool'
46 | if(p) f = max(f, p[p - 1]);
| ^
| |
| std::vector<long long int>
dreaming.cpp:46:24: error: no match for 'operator-' (operand types are 'std::vector<long long int>' and 'int')
46 | if(p) f = max(f, p[p - 1]);
| ~ ^ ~
| | |
| | int
| std::vector<long long int>
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
500 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:500:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::reverse_iterator<_Iterator>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1533 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::move_iterator<_IteratorL>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from dreaming.cpp:2:
/usr/include/c++/10/complex:361:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const std::complex<_Tp>&)'
361 | operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/10/complex:361:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::complex<_Tp>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from dreaming.cpp:2:
/usr/include/c++/10/complex:370:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const _Tp&)'
370 | operator-(const complex<_Tp>& __x, const _Tp& __y)
| ^~~~~~~~
/usr/include/c++/10/complex:370:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::complex<_Tp>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from dreaming.cpp:2:
/usr/include/c++/10/complex:379:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const _Tp&, const std::complex<_Tp>&)'
379 | operator-(const _Tp& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/10/complex:379:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: mismatched types 'const std::complex<_Tp>' and 'int'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from dreaming.cpp:2:
/usr/include/c++/10/complex:456:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&)'
456 | operator-(const complex<_Tp>& __x)
| ^~~~~~~~
/usr/include/c++/10/complex:456:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::complex<_Tp>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/valarray:603,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/valarray:603,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/valarray:603,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/valarray:603,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/valarray:603,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: mismatched types 'const std::_Expr<_Dom1, typename _Dom1::value_type>' and 'int'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::valarray<_Tp>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const std::valarray<_Tp>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from dreaming.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
| ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: mismatched types 'const std::valarray<_Tp>' and 'int'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1164:5: note: candidate: 'template<class _IteratorL, class _IteratorR, class _Container> decltype ((__lhs.base() - __rhs.base())) __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_IteratorL, _Container>&, const __gnu_cxx::__normal_iterator<_IteratorR, _Container>&)'
1164 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1164:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_IteratorL, _Container>'
46 | if(p) f = max(f, p[p - 1]);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1177:5: note: candidate: 'template<class _Iterator, class _Container> typename __gnu_cxx::__normal_iterator<_Iterator, _Container>::difference_type __gnu_cxx::operator-(const __gnu_cxx::__normal_iterator<_Iterator, _Container>&, const __gnu_cxx::__normal_iterator<_Iterator, _Container>&)'
1177 | operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1177:5: note: template argument deduction/substitution failed:
dreaming.cpp:46:26: note: 'std::vector<long long int>' is not derived from 'const __gnu_cxx::__normal_iterator<_Iterator, _Container>'
46 | if(p) f = max(f, p[p - 1]);
| ^
dreaming.cpp:47:8: error: no match for 'operator+' (operand types are 'std::vector<long long int>' and 'int')
47 | if(p + 1 < s.size()) f = max(f, s[p + 1]);
| ~ ^ ~
| | |
| | int
| std::vector<long long int>
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: candidate: 'template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename std::reverse_iterator<_Iterator>::difference_type, const std::reverse_iterator<_Iterator>&)'
508 | operator+(typename reverse_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:508:5: note: template argument deduction/substitution failed:
dreaming.cpp:47:10: note: mismatched types 'const std::reverse_iterator<_Iterator>' and 'int'
47 | if(p + 1 < s.size()) f = max(f, s[p + 1]);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: candidate: 'template<class _Iterator> constexpr std::move_iterator<_IteratorL> std::operator+(typename std::move_iterator<_IteratorL>::difference_type, const std::move_iterator<_IteratorL>&)'
1540 | operator+(typename move_iterator<_Iterator>::difference_type __n,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1540:5: note: template argument deduction/substitution failed:
dreaming.cpp:47:10: note: mismatched types 'const std::move_iterator<_IteratorL>' and 'int'
47 | if(p + 1 < s.size()) f = max(f, s[p + 1]);
| ^
In file included from /usr/include/c++/10/string:55,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from dreaming.cpp:2:
/usr/include/c++/10/bits/basic_string.h:6022:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> std::__cxx11::basic_string<_CharT, _Traits, _Allocator> std::operator+(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6022 | operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6022:5: note: template argument deduction/substitution failed:
dreaming.cpp:47:10: note: 'std::vector<long long int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
47 | if(p + 1 < s.size()) f = max(f, s[p + 1]);
| ^
In file included from /usr/include/c++/10/string:56,
from /usr/include/c++/10/bits/locale_classes.h:40,