| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 651319 | 2022-10-18T09:33:04 Z | therealpain | Dreaming (IOI13_dreaming) | C++14 | Compilation error |
0 ms | 0 KB |
#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);
return ans;
}
Compilation message
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: 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/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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/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/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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/stl_iterator.h:378:5: note: candidate: 'template<class _Iterator> 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/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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/stl_iterator.h:416:5: note: candidate: 'template<class _IteratorL, class _IteratorR> 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/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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/stl_iterator.h:1469:5: note: candidate: 'template<class _IteratorL, class _IteratorR> 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/char_traits.h:39,
from /usr/include/c++/10/ios:40,
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/stl_iterator.h:1519:5: note: candidate: 'template<class _Iterator> 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/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, _Alloc>&, const std::__cxx11::basic_string<_CharT, _Traits, _Alloc>&)'
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, _Alloc>'
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, _Alloc>&, 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, _Alloc>'
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, _Alloc>&)'
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/deque:67,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:68,
from dreaming.cpp:2:
/usr/include/c++/10/bits/stl_deque.h:2292:5: note: candidate: 'template<class _Tp, class _Alloc> bool std::operator>(const std::deque<_Tp, _Alloc>&, const std::deque<_Tp, _Alloc>&)'
2292 | operator>(const deque<_Tp, _Alloc>& __x, const deque<_Tp, _Alloc>& __y)
| ^~~~~~~~
/usr/include/c++/10/bits/stl_deque.h:2292:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::deque<_Tp, _Alloc>'
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/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
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 /usr/include/c++/10/functional:54,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:71,
from dreaming.cpp:2:
/usr/include/c++/10/tuple:1454:5: note: candidate: 'template<class ... _TElements, class ... _UElements> constexpr bool std::operator>(const std::tuple<_Tps ...>&, const std::tuple<_Elements ...>&)'
1454 | operator>(const tuple<_TElements...>& __t,
| ^~~~~~~~
/usr/include/c++/10/tuple:1454:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::tuple<_Tps ...>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/locale_conv.h:41,
from /usr/include/c++/10/locale:43,
from /usr/include/c++/10/iomanip:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from dreaming.cpp:2:
/usr/include/c++/10/bits/unique_ptr.h:846:5: note: candidate: 'template<class _Tp, class _Dp, class _Up, class _Ep> bool std::operator>(const std::unique_ptr<_Tp, _Dp>&, const std::unique_ptr<_Up, _Ep>&)'
846 | operator>(const unique_ptr<_Tp, _Dp>& __x,
| ^~~~~~~~
/usr/include/c++/10/bits/unique_ptr.h:846:5: note: template argument deduction/substitution failed:
dreaming.cpp:13:8: note: 'std::pair<int, int>' is not derived from 'const std::unique_ptr<_Tp, _Dp>'
13 | if (a > b) {a = b; return true;} return false;
| ~~^~~
In file included from /usr/include/c++/10/bits/locale_conv.h:41,
from /usr/include/c++/10/locale:43,
from /usr/include/c++/10/iomanip:43,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:72,
from dreaming.cpp:2:
/usr/include/c++/10/bits/unique_ptr.h:853:5: note: candidate: 'template<class _Tp, class _Dp> bool std::operator>(const std::unique_ptr<_Tp, _Dp>&, std::nullptr_t)'
853 | operator>(const unique_ptr<_Tp, _Dp>& __x, nullptr_t)
| ^~~~~~~~
/usr/include/c++/10/bits/unique_ptr.h:853:5: note: template argument deduction/substitution failed:
/var/lo