Submission #532180

#	Time	Username	Problem	Language	Result	Execution time	Memory
532180		KiriLL1ca	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fr first
#define sc second
#define endl '\n'
#define pb push_back
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)

#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

template <typename T> bool umax (T &a, const T &b) { return (a < b ? a = b, 1 : 0); }
template <typename T> bool umin (T &a, const T &b) { return (a > b ? a = b, 1 : 0); }

template <typename T>
using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 2e5 + 100;

vector <pii> g[N];
ll deep[N], siz[N], mx[N], sum[N];
unordered_set <pii> *sub[N];
/// {sum edges from root, deep}

void calc (int v, int p, int dep, ll depp) {
    siz[v] = 1; mx[v] = -1;
    deep[v] = dep; sum[v] = depp;
    for (auto [u, w] : g[v]) {
        if (u != p) {
            calc(u, v, dep + 1, depp + w);
            siz[v] += siz[u];
            if (mx[v] == -1 || siz[u] > siz[mx[v]]) mx[v] = u;
        }
    }
}

ll ans = 1e18;

void dfs (int v, int p, int k) {
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) dfs(u, v, k);
    }
    if (mx[v] == -1) {
        sub[v] = new set <pii> ();
    }
    else {
        dfs(mx[v], v, k);
        sub[v] = sub[mx[v]];
    }
    sub[v]->insert({sum[v], deep[v]});
    for (auto [u, w] : g[v]) {
        if (u != p && u != mx[v]) {
            for (auto [sumU, deepU] : *sub[u]) {
                if (sumU - sum[v] > k) continue;
                auto it = (*sub[v]).lower_bound({k + sum[v] - (sumU - sum[v]), -2e9});
                if (it != (*sub[v]).end() && it->fr - sum[v] + sumU - sum[v] == k) ans = min(ans, deepU - deep[v] + it->sc - deep[v]);
            }
            for (auto i : *sub[u]) {
                sub[v]->insert(i);
            }
        }
    }
    /// vertical
    auto it = (*sub[v]).lower_bound({k + sum[v], -2e9});
    if (it != (*sub[v]).end() && it->fr - sum[v] == k) ans = min(ans, it->sc - deep[v]);
}

int best_path (int n, int k, int h[][2], int l[]) {
    for (int i = 0; i < n - 1; ++i) {
        g[h[i][0]].pb({h[i][1], l[i]});
        g[h[i][1]].pb({h[i][0], l[i]});
    }
    calc(0, -1, 0, 0);
    dfs(0, -1, k);
    if (ans == 1e18) ans = -1;
    return ans;
}

//signed main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    int n, k; cin >> n >> k;
//    int h[n - 1][2], l[n - 1];
//    for (int i = 0; i < n - 1; ++i) cin >> h[i][0] >> h[i][1];
//    for (int i = 0; i < n - 1; ++i) cin >> l[i];
//    cout << best_path(n, k, h, l);
//    return 0;
//}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int, int)':
race.cpp:54:18: error: cannot convert 'std::set<std::pair<int, int> >*' to 'std::unordered_set<std::pair<int, int> >*' in assignment
   54 |         sub[v] = new set <pii> ();
      |                  ^~~~~~~~~~~~~~~~
      |                  |
      |                  std::set<std::pair<int, int> >*
race.cpp:65:37: error: 'class std::unordered_set<std::pair<int, int> >' has no member named 'lower_bound'
   65 |                 auto it = (*sub[v]).lower_bound({k + sum[v] - (sumU - sum[v]), -2e9});
      |                                     ^~~~~~~~~~~
race.cpp:74:25: error: 'class std::unordered_set<std::pair<int, int> >' has no member named 'lower_bound'
   74 |     auto it = (*sub[v]).lower_bound({k + sum[v], -2e9});
      |                         ^~~~~~~~~~~
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 /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:1:
/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>]'
race.cpp:60:37:   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);
      |         ~~~~~~~^~~~~