Submission #800481

#	Time	Username	Problem	Language	Result	Execution time	Memory
800481		jakobrs	Race (IOI11_race)	C++17	100 / 100	284 ms	54092 KiB

race

#include <map>
#include <vector>

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: In instantiation of 'Map<Key, Value>::Map(Args&& ...) [with Args = {}; Key = int; Value = int]':
race.cpp:56:19:   required from here
race.cpp:8:26: warning: 'Map<int, int>::m' will be initialized after [-Wreorder]
    8 |     std::map<Key, Value> m;
      |                          ^
race.cpp:6:9: warning:   'int Map<int, int>::key_offset' [-Wreorder]
    6 |     Key key_offset;
      |         ^~~~~~~~~~
race.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     Map(Args &&...args)
      |     ^~~

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