Submission #691578

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

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

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

void solve(int x, int p, int K) {
    ans = min(ans, dp[x][K]);
    for(auto [y, w] : adj[x]) {
        if(y == p) continue;
        for(int j = 1; j <= K - 1; ++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);
        }
        solve(y, x, K);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    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, K);
    solve(0, -1, K);


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

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