Submission #1217434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217434		countless	Race (IOI11_race)	C++20	21 / 100	3089 ms	9360 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int best_path(int N, int K, int H[][2], int L[]) {
    ll k = K;
    vector<vector<pair<int, ll>>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        auto [u, v] = H[i];
        ll w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    // [dist, count, at]
    using state = tuple<ll, ll, ll>;

    ll best = LLONG_MAX;
    for (int i = 0; i < N; i++) {
        queue<state> pq;
        vector<bool> vis(N, false);
        pq.push({0, 0, i});
        bool found = false;

        while (!pq.empty()) {
            auto [dist, count, u] = pq.front(); pq.pop();
            
            vis[u] = true;
            for (auto &[v, w] : adj[u]) {
                if (!vis[v] and dist + w <= k) {
                    if (dist + w == k) {
                        best = min(best, count + 1);
                        found = true;
                        break;
                    }

                    pq.push({dist + w, count + 1, v});
                }
            }

            if (found) break;
        }
    }

    if (best == LLONG_MAX) best = -1;

    return best;
}

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