제출 #1306861

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

race

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

static const int INF = 1e9;

int N, K;
vector<pair<int,int>> g[200005];
bool dead[200005];
int sz[200005];
int ans;


void dfs_size(int u, int p) {
    sz[u] = 1;
    for (auto &e : g[u]) {
        int v = e.first;
        if (v == p || dead[v]) continue;
        dfs_size(v, u);
        sz[u] += sz[v];
    }
}


int dfs_centroid(int u, int p, int tot) {
    for (auto &e : g[u]) {
        int v = e.first;
        if (v == p || dead[v]) continue;
        if (sz[v] * 2 > tot)
            return dfs_centroid(v, u, tot);
    }
    return u;
}


void dfs_collect(int u, int p, int dist, int edges,
                 vector<pair<int,int>> &vec) {
    if (dist > K) return;
    vec.push_back({dist, edges});
    for (auto &e : g[u]) {
        int v = e.first, w = e.second;
        if (v == p || dead[v]) continue;
        dfs_collect(v, u, dist + w, edges + 1, vec);
    }
}


void process(int c) {
    unordered_map<int,int> best;
    best.reserve(1024);
    best[0] = 0;

    for (auto &e : g[c]) {
        int v = e.first, w = e.second;
        if (dead[v]) continue;

        vector<pair<int,int>> vec;
        dfs_collect(v, c, w, 1, vec);

        for (auto &x : vec) {
            int d = x.first, cnt = x.second;
            if (best.count(K - d))
                ans = min(ans, cnt + best[K - d]);
        }

        for (auto &x : vec) {
            int d = x.first, cnt = x.second;
            if (!best.count(d))
                best[d] = cnt;
            else
                best[d] = min(best[d], cnt);
        }
    }
}


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

    process(c);

    for (auto &e : g[c]) {
        int v = e.first;
        if (!dead[v])
            decompose(v);
    }
}


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

    for (int i = 0; i < N; i++) {
        g[i].clear();
        dead[i] = false;
    }

    for (int i = 0; i < N - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    decompose(0);

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

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