제출 #1323987

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

race

#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 200005;
const int MAXK = 1000005;
const int INF = 1e9;

vector<pair<int, int>> adj[MAXN];
int sz[MAXN], deleted[MAXN];
int min_depth[MAXK]; // min_depth[d] - d masofaga yetish uchun minimal yo'llar soni
int ans = INF;
int N, K;

// Daraxt o'lchamini hisoblash
int get_sz(int u, int p) {
    sz[u] = 1;
    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first])
            sz[u] += get_sz(edge.first, u);
    }
    return sz[u];
}

// Sentroidni topish
int get_centroid(int u, int p, int total) {
    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first] && sz[edge.first] > total / 2)
            return get_centroid(edge.first, u, total);
    }
    return u;
}

vector<pair<int, int>> current_paths;

// Sentroiddan chiquvchi yo'llarni yig'ish
void get_paths(int u, int p, int d, int dep) {
    if (d > K) return;
    current_paths.push_back({d, dep});
    
    // K - d masofadagi eng yaxshi yo'lni tekshirish
    if (min_depth[K - d] != INF) {
        ans = min(ans, dep + min_depth[K - d]);
    }

    for (auto& edge : adj[u]) {
        if (edge.first != p && !deleted[edge.first])
            get_paths(edge.first, u, d + edge.second, dep + 1);
    }
}

void decompose(int u) {
    int centroid = get_centroid(u, -1, get_sz(u, -1));
    deleted[centroid] = 1;
    min_depth[0] = 0;
    
    vector<int> updated_indices;
    updated_indices.push_back(0);

    for (auto& edge : adj[centroid]) {
        if (!deleted[edge.first]) {
            current_paths.clear();
            get_paths(edge.first, centroid, edge.second, 1);
            for (auto& p : current_paths) {
                min_depth[p.first] = min(min_depth[p.first], p.second);
                updated_indices.push_back(p.first);
            }
        }
    }

    // min_depth massivini tozalash (keyingi sentroid uchun)
    for (int idx : updated_indices) min_depth[idx] = INF;

    for (auto& edge : adj[centroid]) {
        if (!deleted[edge.first]) decompose(edge.first);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    N = n; K = k;
    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]});
    }
    for (int i = 0; i <= K; i++) min_depth[i] = INF;
    
    decompose(0);
    
    return (ans == INF ? -1 : ans);
}

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