제출 #1145821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145821		GGOSHAB	경주 (Race) (IOI11_race)	C++20	0 / 100	2 ms	4936 KiB

race

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

using namespace std;

const int maxn = 200000 + 10, maxk = 1e6 + 10;

const int inf = 1e9 + 10;

typedef long long ll;

typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;

struct per_array {
    array<Pint, maxk> a = {};
    int t = 1;
    int& operator[](int i) {
        if (a[i].second != t) {
            a[i] = {inf, t};
        }
        return a[i].first;
    }
    void clear() {
        t++;
    }
};

vector<Pll> g[maxn];

int w[maxn];
bool used[maxn];
void sizes(int v = 1, int p = -1) {
    w[v] = 1;
    for (auto [u, _] : g[v]) {
        if (u != p && !used[u]) {
            sizes(u, v);
            w[v] += w[u];
        }
    }
}

int centroid(int v, int p, int n) {
    for (auto [u, _] : g[v]) {
        if (u != p && !used[u] && w[u] > n / 2) {
            return centroid(u, v, n);
        }
    }
    return v;
}

void dfs(int v, int p, vector<Pll> &t, ll sum, int h = 1) {
    if (sum < maxk) {
        t.push_back({sum, h});
    }
    for (auto [u, w] : g[v]) {
        if (u != p && !used[u]) {
            dfs(u, v, t, sum + w, h + 1);
        }
    }
}

per_array d;
int solve(int v, int k) {
    sizes(v, v);
    v = centroid(v, v, w[v]);
    used[v] = true;
    int ans = inf;
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            vector<Pll> t;
            dfs(u, v, t, w);
            for (auto [sum, h] : t) {
                if (k - sum >= 0) {
                    ans = min(ans, (int)h + d[k - sum]);
                }
            }
            for (auto [sum, h] : t) {
                d[sum] = min(d[sum], (int)h);
            }
        }
    }

    d.clear();
    for (auto [u, w] : g[v]) {
        if (!used[u]) {
            ans = min(ans, solve(u, k));
        }
    }

    return ans;
}

void add_edge(int v, int u, int w) {
    g[v].push_back({u, w});
    g[u].push_back({v, w});
}

int best_path(int N, int K, int H[][2], int L[]) {
    for (int i = 0; i < N - 1; ++i) {
        add_edge(H[i][0], H[i][1], L[i]);
    }

    int ans = solve(1, K);
    return (ans == inf ? -1 : ans);
}

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