# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
741701 | Alma | Bajka (COCI20_bajka) | 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 <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <queue>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
string s, t;
cin >> n >> m >> s >> t;
vector<unordered_set<pair<int, int>>> graph(n);
for (int i = 0; i < n; i++) {
if (i > 0) {
graph[i].insert({i-1, 1});
graph[i-1].insert({i, 1});
} else if (i < n-1) {
graph[i].insert({i+1, 1});
graph[i+1].insert({i, 1});
}
for (int j = 0; j < n; j++) {
if (s[i] == s[j]) { // add s[j] adjacents
if (j > 0 && i != j-1) {
graph[i].insert({j-1, abs(i - (j-1))});
graph[j-1].insert({i, abs(i - (j-1))});
} else if (j < n-1 && i != j+1) {
graph[i].insert({j+1, abs(i - (j+1))});
graph[j+1].insert({i, abs(i - (j+1))});
}
}
}
}
priority_queue<pair<int, pair<int, int>>> pq; // cost, s_i, t_j
vector<vector<int>> dp(n, vector<int>(m, 1e9));
for (int i = 0; i < n; i++) {
if (s[i] == t[0]) {
pq.push({0, {i, 0}});
dp[i][0] = 0;
}
}
while (!pq.empty()) {
int cost = pq.top().first;
int i = pq.top().second.first;
int j = pq.top().second.second;
pq.pop();
dp[i][j] = min(dp[i][j], cost);
if (j == m-1) {
continue;
}
for (pair<int, int> p: graph[i]) {
int k = p.first;
int c = p.second;
if (s[k] == t[j+1] && cost + c <= dp[k][j+1]) {
pq.push({cost + c, {k, j+1}});
}
}
}
int ans = 1e9;
for (int i = 0; i < n; i++) {
ans = min(ans, dp[i][m-1]);
}
if (ans == 1e9) ans = -1;
cout << ans << '\n';
return 0;
}
Compilation message (stderr)
In file included from /usr/include/c++/10/bits/hashtable.h:35, from /usr/include/c++/10/unordered_map:46, from /usr/include/c++/10/functional:61, from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13, from /usr/include/c++/10/algorithm:74, from bajka.cpp:3: /usr/include/c++/10/bits/hashtable_policy.h: In instantiation of 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_M_hash_code(const _Key&) const [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::__hash_code = long unsigned int]': /usr/include/c++/10/bits/hashtable.h:1807:41: required from 'std::pair<typename std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::iterator, bool> std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_M_insert(_Arg&&, const _NodeGenerator&, std::true_type, std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type) [with _Arg = std::pair<int, int>; _NodeGenerator = std::__detail::_AllocNode<std::allocator<std::__detail::_Hash_node<std::pair<int, int>, true> > >; _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; typename std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::iterator = std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >::iterator; std::true_type = std::integral_constant<bool, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = long unsigned int]' /usr/include/c++/10/bits/hashtable_policy.h:971:22: required from 'std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::__ireturn_type std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::insert(std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::value_type&&) [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::__ireturn_type = std::__detail::_Insert<std::pair<int, int>, std::pair<int, int>, std::allocator<std::pair<int, int> >, std::__detail::_Identity, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true>, true>::__ireturn_type; std::__detail::_Insert<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>::value_type = std::pair<int, int>]' /usr/include/c++/10/bits/unordered_set.h:425:27: required from 'std::pair<typename std::_Hashtable<_Value, _Value, _Alloc, std::__detail::_Identity, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Tp&> > >::value, true, true> >::iterator, bool> std::unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::value_type&&) [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >; typename std::_Hashtable<_Value, _Value, _Alloc, std::__detail::_Identity, _Pred, _Hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<std::__not_<std::__and_<std::__is_fast_hash<_Hash>, std::__is_nothrow_invocable<const _Hash&, const _Tp&> > >::value, true, true> >::iterator = std::__detail::_Hashtable_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::equal_to<std::pair<int, int> >, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >::iterator; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::value_type = std::pair<int, int>]' bajka.cpp:19:28: required from here /usr/include/c++/10/bits/hashtable_policy.h:1377:16: error: static assertion failed: hash function must be invocable with an argument of key type 1377 | static_assert(__is_invocable<const _H1&, const _Key&>{}, | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1379:16: error: no match for call to '(const std::hash<std::pair<int, int> >) (const std::pair<int, int>&)' 1379 | return _M_h1()(__k); | ~~~~~~~^~~~~ In file included from /usr/include/c++/10/bits/alloc_traits.h:33, from /usr/include/c++/10/ext/alloc_traits.h:34, from /usr/include/c++/10/bits/basic_string.h:40, 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/ostream:38, from /usr/include/c++/10/iostream:39, from bajka.cpp:1: /usr/include/c++/10/bits/stl_construct.h: In instantiation of 'void std::_Construct(_Tp*, _Args&& ...) [with _Tp = std::unordered_set<std::pair<int, int> >; _Args = {}]': /usr/include/c++/10/bits/stl_uninitialized.h:567:18: required from 'static _ForwardIterator std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator, _Size) [with _ForwardIterator = std::unordered_set<std::pair<int, int> >*; _Size = long unsigned int; bool _TrivialValueType = false]' /usr/include/c++/10/bits/stl_uninitialized.h:623:20: required from '_ForwardIterator std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator = std::unordered_set<std::pair<int, int> >*; _Size = long unsigned int]' /usr/include/c++/10/bits/stl_uninitialized.h:685:44: required from '_ForwardIterator std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&) [with _ForwardIterator = std::unordered_set<std::pair<int, int> >*; _Size = long unsigned int; _Tp = std::unordered_set<std::pair<int, int> >]' /usr/include/c++/10/bits/stl_vector.h:1606:36: required from 'void std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::unordered_set<std::pair<int, int> >; _Alloc = std::allocator<std::unordered_set<std::pair<int, int> > >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]' /usr/include/c++/10/bits/stl_vector.h:512:9: required from 'std::vector<_Tp, _Alloc>::vector(std::vector<_Tp, _Alloc>::size_type, const allocator_type&) [with _Tp = std::unordered_set<std::pair<int, int> >; _Alloc = std::allocator<std::unordered_set<std::pair<int, int> > >; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::allocator_type = std::allocator<std::unordered_set<std::pair<int, int> > >]' bajka.cpp:15:47: required from here /usr/include/c++/10/bits/stl_construct.h:109:7: error: use of deleted function 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]' 109 | { ::new(static_cast<void*>(__p)) _Tp(std::forward<_Args>(__args)...); } | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ In file included from /usr/include/c++/10/unordered_set:47, from bajka.cpp:4: /usr/include/c++/10/bits/unordered_set.h:135:7: note: 'std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set() [with _Value = std::pair<int, int>; _Hash = std::hash<std::pair<int, int> >; _Pred = std::equal_to<std::pair<int, int> >; _Alloc = std::allocator<std::pair<int, int> >]' is implicitly deleted because the default definition would be ill-formed: 135 | unordered_set() = default; | ^~~~~~~~~~~~~ /usr/include/c++/10/bits/unordered_set.h:135:7: error: use of deleted function 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' In file included from /usr/include/c++/10/unordered_map:46, from /usr/include/c++/10/functional:61, from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13, from /usr/include/c++/10/algorithm:74, from bajka.cpp:3: /usr/include/c++/10/bits/hashtable.h:451:7: note: 'std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' is implicitly deleted because the default definition would be ill-formed: 451 | _Hashtable() = default; | ^~~~~~~~~~ /usr/include/c++/10/bits/hashtable.h:451:7: error: use of deleted function 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' In file included from /usr/include/c++/10/bits/hashtable.h:35, from /usr/include/c++/10/unordered_map:46, from /usr/include/c++/10/functional:61, from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13, from /usr/include/c++/10/algorithm:74, from bajka.cpp:3: /usr/include/c++/10/bits/hashtable_policy.h:1791:5: note: 'std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::pair<int, int> >; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]' is implicitly deleted because the default definition would be ill-formed: 1791 | _Hashtable_base() = default; | ^~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing]' /usr/include/c++/10/bits/hashtable_policy.h:1368:7: note: 'std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base() [with _Key = std::pair<int, int>; _Value = std::pair<int, int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::pair<int, int> >; _H2 = std::__detail::_Mod_range_hashing]' is implicitly deleted because the default definition would be ill-formed: 1368 | _Hash_code_base() = default; | ^~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]' /usr/include/c++/10/bits/hashtable_policy.h:1112:7: note: 'std::__detail::_Hashtable_ebo_helper<_Nm, _Tp, true>::_Hashtable_ebo_helper() [with int _Nm = 1; _Tp = std::hash<std::pair<int, int> >]' is implicitly deleted because the default definition would be ill-formed: 1112 | _Hashtable_ebo_helper() = default; | ^~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<std::pair<int, int> >::hash()' In file included from /usr/include/c++/10/string_view:42, 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/ostream:38, from /usr/include/c++/10/iostream:39, from bajka.cpp:1: /usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<std::pair<int, int> >::hash()' is implicitly deleted because the default definition would be ill-formed: 101 | struct hash : __hash_enum<_Tp> | ^~~~ /usr/include/c++/10/bits/functional_hash.h:101:12: error: no matching function for call to 'std::__hash_enum<std::pair<int, int>, false>::__hash_enum()' /usr/include/c++/10/bits/functional_hash.h:82:7: note: candidate: 'std::__hash_enum<_Tp, <anonymous> >::__hash_enum(std::__hash_enum<_Tp, <anonymous> >&&) [with _Tp = std::pair<int, int>; bool <anonymous> = false]' 82 | __hash_enum(__hash_enum&&); | ^~~~~~~~~~~ /usr/include/c++/10/bits/functional_hash.h:82:7: note: candidate expects 1 argument, 0 provided /usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context 101 | struct hash : __hash_enum<_Tp> | ^~~~ /usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here 83 | ~__hash_enum(); | ^ In file included from /usr/include/c++/10/bits/hashtable.h:35, from /usr/include/c++/10/unordered_map:46, from /usr/include/c++/10/functional:61, from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13, from /usr/include/c++/10/algorithm:74, from bajka.cpp:3: /usr/include/c++/10/bits/hashtable_policy.h:1112:7: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()' 1112 | _Hashtable_ebo_helper() = default; | ^~~~~~~~~~~~~~~~~~~~~ In file included from /usr/include/c++/10/string_view:42, 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/ostream:38, from /usr/include/c++/10/iostream:39, from bajka.cpp:1: /usr/include/c++/10/bits/functional_hash.h:101:12: note: 'std::hash<std::pair<int, int> >::~hash()' is implicitly deleted because the default definition would be ill-formed: 101 | struct hash : __hash_enum<_Tp> | ^~~~ /usr/include/c++/10/bits/functional_hash.h:101:12: error: 'std::__hash_enum<_Tp, <anonymous> >::~__hash_enum() [with _Tp = std::pair<int, int>; bool <anonymous> = false]' is private within this context /usr/include/c++/10/bits/functional_hash.h:83:7: note: declared private here 83 | ~__hash_enum(); | ^ In file included from /usr/include/c++/10/bits/hashtable.h:35, from /usr/include/c++/10/unordered_map:46, from /usr/include/c++/10/functional:61, from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13, from /usr/include/c++/10/algorithm:74, from bajka.cpp:3: /usr/include/c++/10/bits/hashtable_policy.h:1368:7: error: use of deleted function 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()' 1368 | _Hash_code_base() = default; | ^~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1109:12: note: 'std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>::~_Hashtable_ebo_helper()' is implicitly deleted because the default definition would be ill-formed: 1109 | struct _Hashtable_ebo_helper<_Nm, _Tp, true> | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1109:12: error: use of deleted function 'std::hash<std::pair<int, int> >::~hash()' /usr/include/c++/10/bits/hashtable_policy.h:1791:5: error: use of deleted function 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()' 1791 | _Hashtable_base() = default; | ^~~~~~~~~~~~~~~ /usr/include/c++/10/bits/hashtable_policy.h:1341:12: note: 'std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<int, int>, std::__detail::_Identity, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>::~_Hash_code_base()' is implicitly deleted because the default definition would be ill-formed: 1341 | struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1,