Submission #800479

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

race

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

template <typename Key, typename Value>
struct Map {
    Key key_offset;
    Value value_offset;
    std::map<Key, Value> m;

    template <typename... Args>
    Map(Args &&...args)
        : m(std::forward<Args>(args)...), key_offset(), value_offset() {}

    void update_all_keys_by(int offset) { key_offset += offset; }
    void update_all_values_by(int offset) { value_offset += offset; }

    void insert(std::map<Key, Value>::value_type t) { m.insert(t); }
    constexpr inline size_t size() const noexcept { return m.size(); }
};

struct Edge {
    int other;
    int length;
};

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

void merge_into(Map<int, int> &into, Map<int, int> &from) {
    if (into.size() < from.size()) {
        std::swap(into, from);
    }

    for (auto [k_, v_] : from.m) {
        auto k = k_ + from.key_offset;
        auto v = v_ + from.value_offset;

        auto it1 = into.m.find(target - k - into.key_offset);

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

    for (auto [k_, v_] : from.m) {
        auto k = k_ + from.key_offset;
        auto v = v_ + from.value_offset;

        auto it1 = into.m.find(k - into.key_offset);
        if (it1 != into.m.end()) {
            it1->second = std::min(it1->second + into.value_offset, v) -
                          into.value_offset;

        } else {
            into.insert({k - into.key_offset, v - into.value_offset});
        }
    }
}

Map<int, int> dfs(int node, int parent) {
    Map<int, int> result;
    result.insert({0, 0});

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

        Map m = dfs(e.other, node);
        m.update_all_keys_by(e.length);
        m.update_all_values_by(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;
    target = 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:19:17: error: 'std::map<Key, Value, std::less<_Key>, std::allocator<std::pair<const _Key, _Tp> > >::value_type' is not a type
   19 |     void insert(std::map<Key, Value>::value_type t) { m.insert(t); }
      |                 ^~~
race.cpp: In function 'void merge_into(Map<int, int>&, Map<int, int>&)':
race.cpp:58:69: error: cannot convert '<brace-enclosed initializer list>' to 'int'
   58 |             into.insert({k - into.key_offset, v - into.value_offset});
      |                                                                     ^
race.cpp:19:50: note:   initializing argument 1 of 'void Map<Key, Value>::insert(int) [with Key = int; Value = int]'
   19 |     void insert(std::map<Key, Value>::value_type t) { m.insert(t); }
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
race.cpp: In function 'Map<int, int> dfs(int, int)':
race.cpp:65:25: error: cannot convert '<brace-enclosed initializer list>' to 'int'
   65 |     result.insert({0, 0});
      |                         ^
race.cpp:19:50: note:   initializing argument 1 of 'void Map<Key, Value>::insert(int) [with Key = int; Value = int]'
   19 |     void insert(std::map<Key, Value>::value_type t) { m.insert(t); }
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
race.cpp: In instantiation of 'Map<Key, Value>::Map(Args&& ...) [with Args = {}; Key = int; Value = int]':
race.cpp:64:19:   required from here
race.cpp:10:26: warning: 'Map<int, int>::m' will be initialized after [-Wreorder]
   10 |     std::map<Key, Value> m;
      |                          ^
race.cpp:8:9: warning:   'int Map<int, int>::key_offset' [-Wreorder]
    8 |     Key key_offset;
      |         ^~~~~~~~~~
race.cpp:13:5: warning:   when initialized here [-Wreorder]
   13 |     Map(Args &&...args)
      |     ^~~