Submission #1180890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180890		shirokito	Race (IOI11_race)	C++20	9 / 100	140 ms	164724 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
#define el '\n'

const int N = 2e6 + 24;
const ll INF = 1e18;

ll n, k;
vector<pair<ll, ll>> g[N];
ll h[N], d[N]; map<ll, ll> mp[N];

ll res;

void dfs(int u, int pre) {
    for (auto [v, w]: g[u]) {
        if (v == pre) continue;
        d[v] = d[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
    // cout << u << ':' << d[u] << ' ' << h[u] << el;
}

void stl_dfs(int u, int pre) {
    mp[u][d[u]] = h[u];
    for (auto [v, w]: g[u]) {
        if (v == pre) continue;
        stl_dfs(v, u);

        if (mp[u].size() < mp[v].size()) {
            swap(mp[u], mp[v]);
        }

        for (auto [dv, hv]: mp[v]) {
            if (mp[u].count(dv)) {
                mp[u][dv] = min(mp[u][dv], hv);
            } 
            else mp[u][dv] = hv;
        }
    }

    // cout << u << "\n";
    // for (auto [dv, hv]: mp[u]) {
    //     cout << dv << '/' << hv << el;
    // }

    if (mp[u].count(k + d[u])) {
        // cout << "." << mp[u][k + d[u]] - h[u] << el;
        res = min(res, mp[u][k + d[u]] - h[u]);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N; k = K;
    for (int i = 1; i <= n - 1; i++) {
        int u = H[i - 1][0], v = H[i - 1][1];
        ll w = L[i - 1];
        u++, v++;
        // cout << u << ' ' << v << ' ' << w << el;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    res = INF;
    dfs(1, 0);
    stl_dfs(1, 0);

    return (res > n ? -1 : res);
}

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