제출 #1184593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184593		colonelsven	경주 (Race) (IOI11_race)	C++20	100 / 100	285 ms	31992 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 10;
constexpr int K = 1e6 + 10;
constexpr int INF = 1e9 + 10;

struct edge {
    int v, c;
};

vector<edge> adj[N] = {};
bool isRemoved[N] = {};
int d[N] = {};
int minPath[K] = {};
int lastUpdated[K] = {};

int curcentroid = 1;

int ans = INF;

int n, k;

int dfs(int node, int pr=-1) {
    d[node] = 1;
    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v]) {
            d[node] += dfs(ad.v, node);
        }
    }
    return d[node];
}

int getCentroid(int node, int sz, int pr=-1) {
    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v] && d[ad.v] > sz / 2) {
            return getCentroid(ad.v, sz, node);
        }
    }
    return node;
}

void update(int node, int cur, int curd, int pr, bool first) {
    if (cur > k || curd >= ans) return;
    if (first) {
        if (lastUpdated[k - cur] == curcentroid) {
            ans = min(ans, curd + minPath[k - cur]);
        }
    }
    else {
        if (lastUpdated[cur] == curcentroid) {
            minPath[cur] = min(curd, minPath[cur]);
        }
        else {
            lastUpdated[cur] = curcentroid;
            minPath[cur] = curd;
        }
    }

    for (auto ad : adj[node]) {
        if (ad.v != pr && !isRemoved[ad.v]) {
            update(ad.v, cur + ad.c, curd + 1, node, first);
        }
    }
}

void solve(int node) {
    curcentroid++;
    int centroid = getCentroid(node, dfs(node));

    lastUpdated[0] = curcentroid;
    minPath[0] = 0;

    for (auto ad : adj[centroid]) {
        if (!isRemoved[ad.v]) {
            update(ad.v, ad.c, 1, centroid, true);
            update(ad.v, ad.c, 1, centroid, false);
        }
    }

    isRemoved[centroid] = true;
    for (auto ad : adj[centroid]) {
        if (!isRemoved[ad.v]) {
            solve(ad.v);
        }
    }
}

int best_path(int nn, int kk, int H[][2], int L[])
{
    n = nn, k = kk;
    for (int i = 0; i < n - 1; i++) {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    solve(0);
    if (ans == INF) return -1;
    return ans;
}

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