Submission #800345

#	Time	Username	Problem	Language	Result	Execution time	Memory
800345		jakobrs	Race (IOI11_race)	C++17	100 / 100	346 ms	66548 KiB

race

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <iostream>
#include <random>

struct Key {
    int key;
    int lazy;
    int lazy_v;

    Key(int key) : key(key), lazy(0), lazy_v(0) {}
};
struct Mapped {
    int a;

    Mapped() : a(0) {}
    Mapped(int a) : a(a) {}
};

// clang-format off
struct Cmp;

using _Alloc = std::allocator<char>;
using Node_And_It_Traits =
    __gnu_pbds::detail::tree_traits<Key, Mapped, Cmp,
                                    __gnu_pbds::null_node_update,
                                    __gnu_pbds::rb_tree_tag, _Alloc>;
using traits_type = Node_And_It_Traits;

typedef __gnu_pbds::detail::rebind_traits<_Alloc, typename traits_type::node>
    node_alloc_traits;

using value_type = node_alloc_traits::value_type;
using node_pointer = node_alloc_traits::pointer;

void propagate(traits_type::node &node, int lazy, int lazy_v) {
    if (node.m_p_left) {
        node.m_p_left->m_value.second.a += lazy_v;
        const_cast<Key *>(&node.m_p_left->m_value.first)->key += lazy;
        const_cast<Key *>(&node.m_p_left->m_value.first)->lazy += lazy;
        const_cast<Key *>(&node.m_p_left->m_value.first)->lazy_v += lazy_v;
    }
    if (node.m_p_right) {
        node.m_p_right->m_value.second.a += lazy_v;
        const_cast<Key *>(&node.m_p_right->m_value.first)->key += lazy;
        const_cast<Key *>(&node.m_p_right->m_value.first)->lazy += lazy;
        const_cast<Key *>(&node.m_p_right->m_value.first)->lazy_v += lazy_v;
    }
}

void work_on(Key *key_ptr) {
    const constexpr auto offset = offsetof(traits_type::node, m_value.first);

    unsigned char *node_u8_ptr =
        reinterpret_cast<unsigned char *>(const_cast<Key *>(key_ptr));
    traits_type::node *node_ptr = std::launder(
        reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));

    propagate(*node_ptr, key_ptr->lazy, key_ptr->lazy_v);
    key_ptr->lazy = 0;
    key_ptr->lazy_v = 0;
}

struct Cmp {
    bool operator()(const Key &lhs, const Key &rhs) const {
        // This lets you determine which side corresponds to the most recently-inserted value:
        //   static const void *inserting = nullptr;
        //   if (!inserting) inserting = (void *)&rhs;

        if (lhs.lazy || lhs.lazy_v)
            work_on(const_cast<Key *>(&lhs));
        if (rhs.lazy || rhs.lazy_v)
            work_on(const_cast<Key *>(&rhs));

        return lhs.key < rhs.key;
    }
};
// clang-format on

struct map : public __gnu_pbds::tree<Key, Mapped, Cmp, __gnu_pbds::rb_tree_tag,
                                     __gnu_pbds::null_node_update> {
    using base_type =
        __gnu_pbds::tree<Key, Mapped, Cmp, __gnu_pbds::rb_tree_tag,
                         __gnu_pbds::null_node_update>;

    map() : base_type{} {}

    template <typename... Args>
    map(Args &&...args) : base_type(std::forward<Args>(args)...) {}

    map(const map &other) : base_type(other) {}
    map(map &&other) : base_type{} { this->swap(other); }

    map &operator=(const map &other) = delete;
    map &operator=(map &&other) = delete;
};

void update_all_keys_by(map &m, int offset) {
    const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->key += offset;
    const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->lazy += offset;
}
void update_all_values_by(map &m, int offset) {
    m.node_begin().m_p_nd->m_value.second.a += offset;
    const_cast<Key *>(&m.node_begin().m_p_nd->m_value.first)->lazy_v += offset;
}

struct Edge {
    int other;
    int length;
};

Key nonkey{0};

std::vector<std::vector<Edge>> adj;
int best;
int n, k;

void canonicalise_node(map::node_iterator it, map::node_iterator end) {
    propagate(*it.m_p_nd, it.m_p_nd->m_value.first.lazy,
              it.m_p_nd->m_value.first.lazy_v);
    const_cast<Key *>(&it.m_p_nd->m_value.first)->lazy = 0;
    const_cast<Key *>(&it.m_p_nd->m_value.first)->lazy_v = 0;

    if (it.get_l_child() != end) {
        canonicalise_node(it.get_l_child(), end);
    }
    if (it.get_r_child() != end) {
        canonicalise_node(it.get_r_child(), end);
    }
}
void canonicalise(map &m) { canonicalise_node(m.node_begin(), m.node_end()); }

void merge_into(map &into, map &from) {
    if (into.size() < from.size()) {
        into.swap(from);
    }

    canonicalise(from);

    for (auto it = from.begin(); it != from.end(); it++) {
        auto it1 = into.find(k - it->first.key);

        if (it1 != into.end()) {
            best = std::min(best, it->second.a + it1->second.a);
        }
    }

    for (auto it = from.begin(); it != from.end(); it++) {
        auto it1 = into.find(it->first.key);
        if (it1 != into.end()) {
            it1->second.a = std::min(it1->second.a, it->second.a);

        } else {
            into.insert({it->first.key, it->second.a});
        }
    }
}

map dfs(int node, int parent) {
    map result;
    result.insert({0, 0});

    for (Edge e : adj[node]) {
        if (e.other == parent) continue;

        map m = dfs(e.other, node);
        update_all_keys_by(m, e.length);
        update_all_values_by(m, 1);

        merge_into(result, m);
    }

    return result;
}

int best_path(int N, int K, int H[][2], int L[]) {
    adj.resize(N);
    best = N;
    n = N;
    k = K;
    for (int i = 0; i < N - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    dfs(0, -1);

    if (best == N)
        return -1;
    else
        return best;
}

Compilation message (stderr)

race.cpp: In function 'void merge_into(map&, map&)':
race.cpp:57:59: warning: array subscript -2 is outside array bounds of 'const Key [1]' [-Warray-bounds]
   57 |         reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));
      |                                               ~~~~~~~~~~~~^~~~~~~~
race.cpp:149:43: note: while referencing '<anonymous>'
  149 |         auto it1 = into.find(it->first.key);
      |                                           ^
race.cpp:57:59: warning: array subscript -2 is outside array bounds of 'const Key [1]' [-Warray-bounds]
   57 |         reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));
      |                                               ~~~~~~~~~~~~^~~~~~~~
race.cpp:149:43: note: while referencing '<anonymous>'
  149 |         auto it1 = into.find(it->first.key);
      |                                           ^
race.cpp:57:59: warning: array subscript -2 is outside array bounds of 'const Key [1]' [-Warray-bounds]
   57 |         reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));
      |                                               ~~~~~~~~~~~~^~~~~~~~
race.cpp:141:47: note: while referencing '<anonymous>'
  141 |         auto it1 = into.find(k - it->first.key);
      |                                               ^
race.cpp:57:59: warning: array subscript -2 is outside array bounds of 'const Key [1]' [-Warray-bounds]
   57 |         reinterpret_cast<traits_type::node *>(node_u8_ptr - offset));
      |                                               ~~~~~~~~~~~~^~~~~~~~
race.cpp:141:47: note: while referencing '<anonymous>'
  141 |         auto it1 = into.find(k - it->first.key);
      |                                               ^

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57