Submission #977166

#	Time	Username	Problem	Language	Result	Execution time	Memory
977166		saayan007	Race (IOI11_race)	C++17	31 / 100	304 ms	201808 KiB

race

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

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define repd(i, a, b) for(int i = (a); i >= (b); --i)

#define em emplace
#define eb emplace_back

const int mxN = 200010;
const int mxK = 105;
vector<pair<int, int>> adj[mxN];
int dp[mxN][mxK], sm[mxN][mxK];
int ans = mxN;

void dfs(int x, int p, int K) {
    dp[x][0] = 0;
    for(auto [y, w] : adj[x]) {
        if(y == p) continue;
        dfs(y, x, K);
        rep(i, w, K) {
            if(dp[x][i] > 1 + dp[y][i - w]) {
                sm[x][i] = dp[x][i];
                dp[x][i] = 1 + dp[y][i - w];
            }
            else if(sm[x][i] > 1 + dp[y][i - w]) {
                sm[x][i] = 1 + dp[y][i - w];
            }
        }
    }
}

void solve(int x, int p, int K) {
    ans = min(ans, dp[x][K]);
    for(auto [y, w]: adj[x]) {
        if(y == p) continue;
        rep(l, w, K) {
            int here = dp[y][l - w] + 1;
            int there = dp[x][K - l];
            if(K - l - w >= 0 && there == 1 + dp[y][K - l - w])
                there = sm[x][K - l];
            ans = min(ans, here + there);
        }
        solve(y, x, K);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    rep(i, 0, N - 2) {
        adj[H[i][0] + 1].eb(H[i][1] + 1, L[i]);
        adj[H[i][1] + 1].eb(H[i][0] + 1, L[i]);
    }

    rep(i, 0, N) rep(j, 0, K) dp[i][j] = sm[i][j] = mxN;
    dfs(1, -1, K);
    solve(1, -1, K);
    if(ans >= N) ans = -1;
    return ans;
}

Compilation message (stderr)

race.cpp:4:2: warning: #warning notusing64bitintegers [-Wcpp]
    4 | #warning notusing64bitintegers
      |  ^~~~~~~

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