제출 #1313944

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

race

#include "race.h"
#include <vector>
#include <unordered_map>
#include <cassert>
#include <climits>

const int MAXN = 2e5;
using Map = std::unordered_map<long long, int>; // map from sum to smallest dist

struct Edge {
    int node;
    int weight;
};

int n, k;
std::vector<Edge> a[MAXN];
long long sum[MAXN]; // weight sum from root to i
int dist[MAXN]; // edges between root and i
int best_k_path = INT_MAX;

void build_adj(int h[][2], int l[]) {
    for (int i = 0; i < n - 1; i++) {
        a[h[i][0]].push_back({ h[i][1], l[i] });
        a[h[i][1]].push_back({ h[i][0], l[i] });
    }
}

void precalc_dfs(int node, int parent) {
    for (auto [child, weight] : a[node]) {
        if (child == parent) continue;

        sum[child] = sum[node] + weight;
        dist[child] = dist[node] + 1;
        precalc_dfs(child, node);
    }
}

// returns smallest dist of sum k
int find_smallest_k_path(const Map& dst, const Map& src, int node) {
    assert(dst.size() >= src.size());
    int res = INT_MAX;

    for (auto [s, d] : src) {
        if (dst.count(k - s + 2 * sum[node])) {
            res = std::min(res, dst.at(k - s + 2 * sum[node]) + d - 2 * dist[node]);
        }
    }

    return res;
}

void merge_into(Map& dst, const Map& src) {
    assert(dst.size() >= src.size());
    
    for (auto [s, d] : src) {
        if (dst.count(s)) {
            dst[s] = std::min(dst[s], d);
        } else {
            dst[s] = d;
        }
    }
}

Map dfs(int node, int parent) {
    Map res;
    res[sum[node]] = dist[node];

    for (auto [child, _] : a[node]) {
        if (child == parent) continue;
        Map m = dfs(child, node);

        if (m.size() > res.size()) {
            std::swap(res, m);
        }

        best_k_path = std::min(best_k_path, find_smallest_k_path(res, m, node));
        merge_into(res, m);
    }

    return res;
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    build_adj(H, L);
    precalc_dfs(0, -1);
    dfs(0, -1);
    return best_k_path != INT_MAX ? best_k_path : -1;
}

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