| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651317 | therealpain | Dreaming (IOI13_dreaming) | C++17 | Compilation error | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dreaming.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define getbit(x, i) (((x) >> (i)) & 1)
#define all(x) x.begin(), x.end()
#define TASK "DREAMING"
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const long long inf = 1e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 7;
long long dp[N][2], g[N], d[N], ans;
pair <int, int> center_dist;
vector <pair <int, int>> a[N];
bool visited[N];
int n, m, l;
void dfs1(int u, int p) {
visited[u] = 1;
for (auto i : a[u]) {
if (i.fi == p) continue;
int v = i.fi, w = i.se;
dfs1(v, u);
if (dp[u][0] < dp[v][0] + w) {
dp[u][1] = dp[u][0];
dp[u][0] = dp[v][0] + w;
} else if (dp[v][0] + w > dp[u][1])
dp[u][1] = dp[v][0] + w;
}
maxi(ans, dp[u][0] + dp[u][1]);
}
void dfs2(int u, int p, long long w) {
if (p != u) g[u] = max(g[p] + w, (dp[u][0] + w == dp[p][0]) ? dp[p][1] + w : dp[p][0]);
mini(center_dist, mp(max(g[u], dp[u][0]), u));
for (auto i : a[u]) {
if (i.fi == p) continue;
int v = i.fi, w2 = i.se;
dfs2(v, u, w2);
}
}
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) {
int u = ++A[i], v = ++B[i], w = T[i];
a[u].push_back({v, w});
a[v].push_back({u, w});
}
vector <pair <int, int>> v;
for (int i = 1; i <= n; ++i) {
if (visited[i] == 1) continue;
dfs1(i, i);
center_dist = mp(1e9 + 9, 0);
dfs2(i, i, 0);
v.push_back(center_dist);
}
sort(all(v), greater <pair <int, int>>());
for (int i = 1; i < v.size(); ++i) {
a[v[0].se].emplace_back(v[i].se, l);
a[v[i].se].emplace_back(v[0].se, l);
}
memset(dp, 0, sizeof dp);
ans = 0;
dfs1(1, 1);
cout << ans;
}
Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int i = 1; i < v.size(); ++i) {
| ~~^~~~~~~~~~
dreaming.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
80 | }
| ^
dreaming.cpp: In instantiation of 'bool mini(T1&, T2) [with T1 = std::pair<int, int>; T2 = std::pair<long long int, int>]':
dreaming.cpp:46:47: required from here
dreaming.cpp:13:8: error: no match for 'operator>' (operand types are 'std::pair<int, int>' and 'std::pair<long long int, int>')
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1108:5: note: candidate: 'template<class _BiIter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const std::__cxx11::sub_match<_BiIter>&)'
1108 | operator>(const sub_match<_BiIter>& __lhs, const sub_match<_BiIter>& __rhs)
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1108:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1168:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&, const std::__cxx11::sub_match<_BiIter>&)'
1168 | operator>(const __sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1168:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1261:5: note: candidate: 'template<class _Bi_iter, class _Ch_traits, class _Ch_alloc> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, std::__cxx11::__sub_match_string<_Bi_iter, _Ch_traits, _Ch_alloc>&)'
1261 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1261:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1335:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type*, const std::__cxx11::sub_match<_BiIter>&)'
1335 | operator>(typename iterator_traits<_Bi_iter>::value_type const* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1335:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1429:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type*)'
1429 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1429:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1505:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const typename std::iterator_traits<_Iter>::value_type&, const std::__cxx11::sub_match<_BiIter>&)'
1505 | operator>(typename iterator_traits<_Bi_iter>::value_type const& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1505:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<long long int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/regex:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:110,
from dreaming.cpp:2:
/usr/include/c++/10/bits/regex.h:1605:5: note: candidate: 'template<class _Bi_iter> bool std::__cxx11::operator>(const std::__cxx11::sub_match<_BiIter>&, const typename std::iterator_traits<_Iter>::value_type&)'
1605 | operator>(const sub_match<_Bi_iter>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/regex.h:1605:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::sub_match<_BiIter>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
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_pair.h:502:5: note: candidate: 'template<class _T1, class _T2> constexpr bool std::operator>(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)'
502 | operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:502:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: deduced conflicting types for parameter '_T1' ('int' and 'long long int')
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:378:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)'
378 | operator>(const reverse_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:378:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:416:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
416 | operator>(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:416:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::reverse_iterator<_Iterator>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:1469:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
1469 | operator>(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1469:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:1519:5: note: candidate: 'template<class _Iterator> constexpr bool std::operator>(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&)'
1519 | operator>(const move_iterator<_Iterator>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1519:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::move_iterator<_IteratorL>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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/string_view:563:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::basic_string_view<_CharT, _Traits>)'
563 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:563:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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/string_view:569:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::basic_string_view<_CharT, _Traits>, std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >)'
569 | operator> (basic_string_view<_CharT, _Traits> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:569:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/basic_string.h:48,
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/string_view:576:5: note: candidate: 'template<class _CharT, class _Traits> constexpr bool std::operator>(std::__type_identity_t<std::basic_string_view<_CharT, _Traits> >, std::basic_string_view<_CharT, _Traits>)'
576 | operator> (__type_identity_t<basic_string_view<_CharT, _Traits>> __x,
| ^~~~~~~~
/usr/include/c++/10/string_view:576:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<long long int, int>' is not derived from 'std::basic_string_view<_CharT, _Traits>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:6305:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6305 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6305:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:6318:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&, const _CharT*)'
6318 | operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6318:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
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:6330:5: note: candidate: 'template<class _CharT, class _Traits, class _Alloc> bool std::operator>(const _CharT*, const std::__cxx11::basic_string<_CharT, _Traits, _Allocator>&)'
6330 | operator>(const _CharT* __lhs,
| ^~~~~~~~
/usr/include/c++/10/bits/basic_string.h:6330:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: mismatched types 'const _CharT*' and 'std::pair<int, int>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/tuple:39,
from /usr/include/c++/10/functional:54,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from dreaming.cpp:2:
/usr/include/c++/10/array:293:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> bool std::operator>(const std::array<_Tp, _Nm>&, const std::array<_Tp, _Nm>&)'
293 | operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two)
| ^~~~~~~~
/usr/include/c++/10/array:293:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::array<_Tp, _Nm>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from