Submission #691577

#	Time	Username	Problem	Language	Result	Execution time	Memory
691577		zeroesandones	Race (IOI11_race)	C++17	9 / 100	116 ms	93372 KiB

race

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

using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;

const int mxN = 2e5 + 5;
const ll inf = 1e15;
ll dp[mxN][105];
vector<pi> adj[mxN];

void dfs(int x, int p) {
    fill(dp[x], dp[x] + 105, inf);
    dp[x][0] = 0;

    for(auto [y, w] : adj[x]) {
        if(y == p) continue;
        dfs(y, x);
        for(int j = w; j <= 100; ++j) {
            dp[x][j] = min(dp[x][j], dp[y][j - w] + 1);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    ll ans = inf;
    for(int i = 0; i < N - 1; ++i) {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    
    dfs(0, -1);
    for(int i = 0; i < N; ++i) {
        ans = min(ans, dp[i][K]);
    }

    return (ans < inf ? ans : -1);
}

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