제출 #1283121

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283121		diep38	경주 (Race) (IOI11_race)	C++17	43 / 100	3096 ms	30280 KiB

race

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

static const int INF = 1e9;

static int N_, K_;
static vector<vector<pair<int,int>>> g;
static vector<int> sz;
static vector<char> dead;
static int answer;

static void dfs_size(int u, int p){
    sz[u] = 1;
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}
static int find_centroid(int u, int p, int tot){
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        if (sz[v] * 2 > tot) return find_centroid(v, u, tot);
    }
    return u;
}

static void collect(int u, int p, int dist, int edges, vector<pair<int,int>>& vec){
    if (dist > K_) return;
    vec.emplace_back(dist, edges);
    for (auto [v, w] : g[u]) if (v != p && !dead[v]){
        collect(v, u, dist + w, edges + 1, vec);
    }
}

static void solve_centroid(int c){
    vector<int> best(K_ + 1, INF);
    best[0] = 0;                

    for (auto [v, w] : g[c]) if (!dead[v]){
        vector<pair<int,int>> buf;
        collect(v, c, w, 1, buf);

        for (auto [d, e] : buf){
            if (d <= K_){
                int need = K_ - d;
                if (best[need] != INF) answer = min(answer, e + best[need]);
            }
        }
        for (auto [d, e] : buf){
            if (d <= K_) best[d] = min(best[d], e);
        }
    }
}

static void decompose(int entry){
    dfs_size(entry, -1);
    int c = find_centroid(entry, -1, sz[entry]);
    dead[c] = 1;

    solve_centroid(c);

    for (auto [v, w] : g[c]) if (!dead[v]){
        decompose(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    N_ = N; K_ = K;
    if (K_ == 0) return 0;

    g.assign(N_, {});
    sz.assign(N_, 0);
    dead.assign(N_, 0);
    answer = INF;

    for (int i = 0; i < N_ - 1; ++i){
        int u = H[i][0], v = H[i][1], w = L[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    decompose(0);
    return (answer == INF ? -1 : answer);
}

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