Submission #1180895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180895		shirokito	Race (IOI11_race)	C++20	21 / 100	3099 ms	147528 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, ll cnt, ll W) {
    if (W == k) res = min(res, cnt);
    for (auto [v, w]: g[u]) {
        if (v == pre) continue;
        dfs(v, u, cnt + 1, W + w);
    }
}

// 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;

    for (int i = 1; i <= n; i++) {
        dfs(i, 0, 0, 0);
    }

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

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