Submission #559222

#	Time	Username	Problem	Language	Result	Execution time	Memory
559222		_karan_gandhi	Race (IOI11_race)	C++17	9 / 100	119 ms	51892 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define all(v) v.begin(), v.end()
#define pl(var) " [" << #var << ": " << (var) << "] "

vector<vector<pair<int, int>>> adj;
vector<vector<int>> dp;
// multiset<int> distances;
int k;
int ans = -1;

void dfs(int u, int par) {
    // cout << pl(u) << endl;
    for (auto [v, wt] : adj[u]) {
        if (v == par) continue;
        // cout << pl(v) << pl(wt) << endl;
        dfs(v, u);

        if (wt <= k) dp[u][wt] = 1;
        for (int i = wt + 1; i <= k; i++) {
            if (dp[u][i] != -1) dp[u][i] = min(dp[u][i], ((dp[v][i - wt] == -1) ? dp[u][i] : (dp[v][i - wt] + 1)));
            else dp[u][i] = dp[v][i - wt] + (dp[v][i - wt] != -1 ? 1 : 0);
        }

        // cout << pl(dp[u][k]) << endl;

        if (ans != -1) ans = min(ans, dp[u][k] == -1 ? ans : dp[u][k]);
        else ans = dp[u][k];
    }
}

void dfs1(int u, int par) {
    for (int i = 0; i <= k; i++) {
        ans = min(ans, dp[u][k] + dp[u][k - 1]);
    }
}

int best_path(int n, int _k, int edges[][2], int weight[]) {
    adj = vector<vector<pair<int, int>>>(n);
    k = _k;
    // ans = n - 1;
    dp = vector<vector<int>>(n, vector<int>(k + 1, -1));

    for (int i = 0; i < n - 1; i++) {
        adj[edges[i][0]].emplace_back(edges[i][1], weight[i]);
        adj[edges[i][1]].emplace_back(edges[i][0], weight[i]);
    }
    dfs(0, 0);
    // cout << pl(dp[0][3]) << endl;

    return ans;
}

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