Submission #1304524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304524		disfyy	경주 (Race) (IOI11_race)	C++20	21 / 100	3094 ms	47364 KiB

race

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

using ll = long long;

const ll N = 500005;
const ll INF = (ll)2e18;

ll up[N][23], dp[N], sum[N][23];
ll tin[N], tout[N], timer;
vector<pair<ll,ll>> g[N];

void dfs(ll v, ll p) {
    dp[v] = dp[p] + 1;
    tin[v] = ++timer;

    for (int i = 1; i <= 22; i++) {
        up[v][i] = up[ up[v][i-1] ][i-1];
        sum[v][i] = sum[v][i-1] + sum[ up[v][i-1] ][i-1];
    }

    for (auto it : g[v]) {
        ll to = it.first;
        ll w  = it.second;
        if (to != p) {
            up[to][0] = v;
            sum[to][0] = w;
            dfs(to, v);
        }
    }
    tout[v] = timer;
}

bool check(ll u, ll v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

ll lca(ll u, ll v) {
    if (check(u, v)) return u;
    if (check(v, u)) return v;
    for (int i = 22; i >= 0; i--) {
        if (!check(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

ll calc(ll u, ll need) {
    ll ans = 0;
    for (int i = 22; i >= 0; i--) {
        if (need & (1LL << i)) {
            ans += sum[u][i];
            u = up[u][i];
        }
    }
    return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; i++) {
        ll u = H[i][0] + 1;
        ll v = H[i][1] + 1;
        ll w = L[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    up[1][0] = 1;
    dfs(1, 0);
    ll mn = INF;
    for (int i = 1; i <= N; i++) {
        for (int j = i + 1; j <= N; j++) {
            ll r = lca(i, j);
            ll dist = calc(i, dp[i] - dp[r]) + calc(j, dp[j] - dp[r]);
            if (dist == K) {
                mn = min(mn, dp[i] + dp[j] - 2 * dp[r]);
            }
        }
    }
    if (mn == INF) return -1;
    return (int)mn;
}

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