Submission #1024311

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024311		eysbutno	Race (IOI11_race)	C++17	100 / 100	362 ms	96172 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = array<int, 2>;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

int best_path(int n, int k, int h[][2], int l[]) {
    vector<vector<pii>> adj(n);
    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]});
    }
    vector<ll> f(n);
    vector<int> dep(n);
    const auto build = [&](int u, int p, auto &&self) -> void {
        for (auto [v, w] : adj[u]) {
            if (v == p) { continue; }
            f[v] = f[u] + w;
            dep[v] = dep[u] + 1;
            self(v, u, self); 
        }
    };
    build(0, -1, build);
    vector<map<ll, int>> mp(n);
    const int INF = 1e9;
    int res = INF;
    const auto merge = [&](int i, int j) -> void {
        if (mp[j].count(f[i] + k)) {
            res = min(res, mp[j][f[i] + k] - dep[i]);
        }
        ll need = k + f[i] * 2;
        int sub = 2 * dep[i];
        if (sz(mp[i]) < sz(mp[j])) {
            swap(mp[i], mp[j]);
        }
        for (auto [len, dx] : mp[j]) {
            if (mp[i].count(need - len)) {
                res = min(res, dx + mp[i][need - len] - sub);
            }
        }
        for (auto [len, dx] : mp[j]) {
            if (mp[i].count(len)) {
                mp[i][len] = min(mp[i][len], dx);
            } else {
                mp[i][len] = dx;
            }
        }
    };
    const auto dfs = [&](int u, int p, auto &&self) -> void {
        for (auto [v, w] : adj[u]) {
            if (v == p) { continue; }
            self(v, u, self);
            merge(u, v);
        }
        mp[u][f[u]] = dep[u];
    };
    dfs(0, -1, dfs);
    return res < INF ? res : -1;
}

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