제출 #1363338

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

race

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

const int MAXN = 200000 + 5;
const int INF = 1e9;

int n, k;
vector<pair<int, int>> ke[MAXN];
bool removed[MAXN];
int subtree[MAXN];
int ans;

vector<int> best;
vector<int> used;

int getsub(int u, int p) {
    subtree[u] = 1;

    for (auto [v, w] : ke[u]) {
        if (v == p || removed[v]) continue;
        subtree[u] += getsub(v, u);
    }

    return subtree[u];
}

int getCentroid(int u, int p, int total) {
    for (auto [v, w] : ke[u]) {
        if (v == p || removed[v]) continue;

        if (subtree[v] * 2 > total) {
            return getCentroid(v, u, total);
        }
    }

    return u;
}

void dfs_collect(int u, int p, int depth, int dist, vector<pair<int, int>>& nodes) {
    if (dist > k) return;

    nodes.push_back({dist, depth});

    for (auto [v, w] : ke[u]) {
        if (v == p || removed[v]) continue;
        dfs_collect(v, u, depth + 1, dist + w, nodes);
    }
}

void process(int cen) {
    used.clear();

    best[0] = 0;
    used.push_back(0);

    for (auto [v, w] : ke[cen]) {
        if (removed[v]) continue;

        vector<pair<int, int>> nodes;
        dfs_collect(v, cen, 1, w, nodes);

        for (auto [dist, depth] : nodes) {
            int need = k - dist;

            if (need >= 0 && best[need] != INF) {
                ans = min(ans, depth + best[need]);
            }
        }

        for (auto [dist, depth] : nodes) {
            if (best[dist] == INF) {
                used.push_back(dist);
            }

            best[dist] = min(best[dist], depth);
        }
    }

    for (int x : used) {
        best[x] = INF;
    }
}

void decompose(int u) {
    int total = getsub(u, -1);
    int cen = getCentroid(u, -1, total);

    process(cen);

    removed[cen] = true;

    for (auto [v, w] : ke[cen]) {
        if (!removed[v]) {
            decompose(v);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    ans = INF;

    best.assign(k + 1, INF);

    for (int i = 0; i < n; i++) {
        ke[i].clear();
        removed[i] = false;
        subtree[i] = 0;
    }

    for (int i = 0; i < n - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];

        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }

    decompose(0);

    if (ans == INF) return -1;
    return ans;
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 12 / 12
• 서브태스크 3: 22 / 22
• 서브태스크 4: 57 / 57