Submission #691591

#	Time	Username	Problem	Language	Result	Execution time	Memory
691591		zeroesandones	Race (IOI11_race)	C++17	9 / 100	214 ms	262144 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>;

#define pb emplace_back

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

void dfs(int x, int p) {
    for(auto [y, w] : adj[x]) {
        if(y == p) continue;
        dfs(y, x);
        for(int j = 1; j <= k; ++j) {
            if(j - w >= 0) {
                if(dp[x][j] > 1 + dp[y][j - w]) {
                    dp2[x][j] = dp[x][j];
                    dp[x][j] = dp[y][j - w] + 1;
                } else if(dp2[x][j] > 1 + dp[y][j - w]) {
                    dp2[x][j] = dp[y][j - w] + 1;
                }
            }
        }
    }

    dp[x][0] = 0;
}

void dfs2(int x, int p) {
    ans = min(ans, dp[x][k]);
    for(auto [y, w] : adj[x]) {
        if(y == p) continue;
        for(int j = 1; j < k; ++j) {
            if(j - w < 0) continue;
            ll one = dp[y][j - w] + 1;
            ll two = dp[x][k - j];
            if(k - j - w >= 0 && dp[y][k - j - w] + 1 == two)
                two = dp2[x][k - j];
            ans = min(ans, one + two);
        }
        dfs2(y, x);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    for(int i = 0; i < N - 1; ++i) {
        adj[H[i][0]].pb(H[i][1], L[i]);
        adj[H[i][1]].pb(H[i][0], L[i]);
    }

    k = K;
    for(int i = 0; i <= N; ++i) {
        for(int j = 0; j <= K; ++j) {
            dp[i][j] = dp2[i][j] = inf;
        }
    }

    dfs(0, -1);
    dfs2(0, -1);

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

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