Submission #977204

#	Time	Username	Problem	Language	Result	Execution time	Memory
977204		saayan007	Race (IOI11_race)	C++17	0 / 100	2 ms	11608 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 = 2e5L + 10;
const int mxK = 1e6L + 10;
int n, k;
vector<pair<int, int>> adj[mxN];
int ans = mxN;
int sz[mxN];
bool proc[mxN] = {};
int dp[mxK];

int get_sz(int x, int p) {
    sz[x] = 1;
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        sz[x] += get_sz(y, x);
    }
    return sz[x];
}

int get_cen(int x, int p, int tot) {
    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p || sz[y] * 2 <= tot) continue;
        return get_cen(y, x, tot);
    }
    return x;
}

void dfs(int x, int p, int dep, int dis, bool flag) {
    if(dis > k) return;
    if(flag == 0) {
        if(dp[k - dis] != mxN) ans = min(ans, dep + dp[k - dis]);
    }
    else if(flag == 1) {
        dp[dis] = min(dp[dis], dep);
    }
    else {
        dp[dis] = mxN;
    }

    for(auto [y, w] : adj[x]) {
        if(proc[y] || y == p) continue;
        dfs(y, x, dep + 1, dis + w, flag);
    }
}

void solve(int x = 1, int p = -1) {
    int c = get_cen(x, p, get_sz(x, p));
    dp[0] = 0;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 0);
        dfs(d, c, 1, w, 1);
    }
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        dfs(d, c, 1, w, 2);
    }
    dp[0] = mxN;
    proc[c] = 1;
    for(auto [d, w] : adj[c]) {
        if(proc[d]) continue;
        solve(d, c);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    rep(i, 0, K) dp[i] = mxN;
    n = N; k = K;
    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]);
    }

    solve();
    return (ans > n - 1 ? -1 : ans);
}

Compilation message (stderr)

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

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