| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 800480 | jakobrs | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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;
}