Submission #515843

#	Time	Username	Problem	Language	Result	Execution time	Memory
515843		tabr	Race (IOI11_race)	C++17	100 / 100	569 ms	97144 KiB

race

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int best_path(int n, int k, int h[][2], int l[]) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        g[h[i][0]].emplace_back(i);
        g[h[i][1]].emplace_back(i);
    }
    int ans = n;
    vector<int> depth(n);
    vector<long long> dist(n);
    vector<map<long long, int>> a(n);
    auto dfs = [&](auto dfs, int v, int p) -> void {
        vector<int> c;
        for (int id : g[v]) {
            int to = v ^ h[id][0] ^ h[id][1];
            if (to == p) {
                continue;
            }
            c.emplace_back(to);
            depth[to] = depth[v] + 1;
            dist[to] = dist[v] + l[id];
            dfs(dfs, to, v);
            long long t = dist[v] + k;
            if (a[to].count(t)) {
                ans = min(ans, a[to][t] - depth[v]);
            }
        }
        if (c.empty()) {
            a[v][dist[v]] = depth[v];
            return;
        }
        sort(c.begin(), c.end(), [&](int i, int j) {
            return a[i].size() > a[j].size();
        });
        swap(a[v], a[c[0]]);
        a[v][dist[v]] = depth[v];
        for (int i = 1; i < (int) c.size(); i++) {
            for (auto q : a[c[i]]) {
                long long t = 2 * dist[v] - q.first + k;
                if (a[v].count(t)) {
                    ans = min(ans, a[v][t] + q.second - 2 * depth[v]);
                }
            }
            for (auto q : a[c[i]]) {
                if (!a[v].count(q.first)) {
                    a[v][q.first] = n;
                }
                a[v][q.first] = min(a[v][q.first], q.second);
            }
        }
    };
    dfs(dfs, 0, -1);
    if (ans == n) {
        ans = -1;
    }
    return ans;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

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