Submission #800480

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

race

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() {}
};

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.m.size() < from.m.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.m.insert({k - into.key_offset, v - into.value_offset});
        }
    }
}

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

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

        Map m = dfs(e.other, node);
        m.key_offset += e.length;
        m.value_offset += 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:5:10: error: 'map' in namespace 'std' does not name a template type
    5 |     std::map<Key, Value> m;
      |          ^~~
race.cpp:1:1: note: 'std::map' is defined in header '<map>'; did you forget to '#include <map>'?
  +++ |+#include <map>
    1 | template <typename Key, typename Value>
race.cpp: In constructor 'Map<Key, Value>::Map(Args&& ...)':
race.cpp:9:11: error: class 'Map<Key, Value>' does not have any field named 'm'
    9 |         : m(std::forward<Args>(args)...), key_offset(), value_offset() {}
      |           ^
race.cpp:9:18: error: 'forward' is not a member of 'std'
    9 |         : m(std::forward<Args>(args)...), key_offset(), value_offset() {}
      |                  ^~~~~~~
race.cpp:1:1: note: 'std::forward' is defined in header '<utility>'; did you forget to '#include <utility>'?
  +++ |+#include <utility>
    1 | template <typename Key, typename Value>
race.cpp:9:30: error: expected primary-expression before '>' token
    9 |         : m(std::forward<Args>(args)...), key_offset(), value_offset() {}
      |                              ^
race.cpp: At global scope:
race.cpp:17:6: error: 'vector' in namespace 'std' does not name a template type
   17 | std::vector<std::vector<Edge>> adj;
      |      ^~~~~~
race.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | template <typename Key, typename Value>
race.cpp: In function 'void merge_into(Map<int, int>&, Map<int, int>&)':
race.cpp:22:14: error: 'struct Map<int, int>' has no member named 'm'
   22 |     if (into.m.size() < from.m.size()) {
      |              ^
race.cpp:22:30: error: 'struct Map<int, int>' has no member named 'm'
   22 |     if (into.m.size() < from.m.size()) {
      |                              ^
race.cpp:23:14: error: 'swap' is not a member of 'std'
   23 |         std::swap(into, from);
      |              ^~~~
race.cpp:26:31: error: 'struct Map<int, int>' has no member named 'm'
   26 |     for (auto [k_, v_] : from.m) {
      |                               ^
race.cpp:30:25: error: 'struct Map<int, int>' has no member named 'm'
   30 |         auto it1 = into.m.find(target - k - into.key_offset);
      |                         ^
race.cpp:32:25: error: 'struct Map<int, int>' has no member named 'm'
   32 |         if (it1 != into.m.end()) {
      |                         ^
race.cpp:33:25: error: 'min' is not a member of 'std'
   33 |             best = std::min(best, v + it1->second + into.value_offset);
      |                         ^~~
race.cpp:37:31: error: 'struct Map<int, int>' has no member named 'm'
   37 |     for (auto [k_, v_] : from.m) {
      |                               ^
race.cpp:41:25: error: 'struct Map<int, int>' has no member named 'm'
   41 |         auto it1 = into.m.find(k - into.key_offset);
      |                         ^
race.cpp:42:25: error: 'struct Map<int, int>' has no member named 'm'
   42 |         if (it1 != into.m.end()) {
      |                         ^
race.cpp:43:32: error: 'min' is not a member of 'std'
   43 |             it1->second = std::min(it1->second + into.value_offset, v) -
      |                                ^~~
race.cpp:47:18: error: 'struct Map<int, int>' has no member named 'm'
   47 |             into.m.insert({k - into.key_offset, v - into.value_offset});
      |                  ^
race.cpp: In function 'Map<int, int> dfs(int, int)':
race.cpp:54:12: error: 'struct Map<int, int>' has no member named 'm'
   54 |     result.m.insert({0, 0});
      |            ^
race.cpp:56:19: error: 'adj' was not declared in this scope
   56 |     for (Edge e : adj[node]) {
      |                   ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:70:5: error: 'adj' was not declared in this scope
   70 |     adj.resize(N);
      |     ^~~