Submission #1075418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075418		juicy	Race (IOI11_race)	C++17	100 / 100	395 ms	98060 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

int best_path(int n, int k, int H[][2], int L[]) {
    vector<vector<array<int, 2>>> g(n);
    for (int i = 0; i < n; ++i) {
        for (auto it : {0, 1}) {
            g[H[i][it]].push_back({H[i][it ^ 1], i});
        }
    }
    vector<map<long long, int>> mp(n);
    function<int(int, int, int, long long)> dfs = [&](int u, int p, int h, long long dep) {
        int res = n + 1;
        mp[u][dep] = h;
        for (auto [v, ind] : g[u]) {
            if (v != p) {
                res = min(res, dfs(v, u, h + 1, dep + L[ind]));
                if (mp[u].size() < mp[v].size()) {
                    mp[u].swap(mp[v]);
                }
                for (auto [x, y] : mp[v]) {
                    if (mp[u].count(k + 2 * dep - x)) {
                        res = min(res, y + mp[u][k + 2 * dep - x] - 2 * h);
                    }
                }
                for (auto [x, y] : mp[v]) {
                    if (!mp[u].count(x)) {
                        mp[u][x] = y;
                    } else {
                        mp[u][x] = min(mp[u][x], y);
                    }
                }
            }
        }
        return res;
    };
    auto res = dfs(0, 0, 0, 0);
    return res == n + 1 ? -1 : res;
}

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