제출 #639492

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

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

vector<vector<pair<size_t, long>>> g;

vector<size_t> subtr_size;
vector<bool> visited;

vector<size_t> paths;
vector<pair<size_t, long>> cdis;
vector<size_t> modified;
size_t min_path = SIZE_MAX;

size_t get_size(size_t u, size_t p)
{
    size_t total = 1;

    for (auto const &[v, w] : g[u])
        if (!visited[v] && v != p)
            total += get_size(v, u);

    subtr_size[u] = total;
    return total;
}

size_t find_centroid(size_t u, size_t p, size_t n)
{
    for (auto const &[v, w] : g[u])
        if (!visited[v] && v != p && subtr_size[v] > n / 2)
            return find_centroid(v, u, n);

    return u;
}

void find_path_lengths(size_t u, size_t k, size_t p = -1, size_t l = 0, size_t h = 0)
{
    if (l > k)
        return;

    if (h < paths[l])
    {
        paths[l] = h;
        modified.push_back(l);
    }

    for (auto const &[v, w] : g[u])
        if (!visited[v] && v != p)
            find_path_lengths(v, k, u, l + w, h + 1);
}

void find_cdis(size_t u, size_t k, size_t p = -1, size_t l = 0, size_t h = 0)
{
    if (l > k)
        return;

    cdis.push_back(make_pair(h, l));

    for (auto const &[v, w] : g[u])
        if (!visited[v] && v != p)
            find_cdis(v, k, u, l + w, h + 1);
}

void decompose(size_t u, size_t k)
{
    size_t n = get_size(u, -1);
    size_t c = find_centroid(u, -1, n);

    visited[c] = 1;

    // Search for all path lengths <= k in each adjacent subtree of the current centroid.
    // If possible, match them up and update the current minimum.

    paths[0] = 0;

    for (auto const &[v, w] : g[c])
    {
        find_cdis(v, k, c, w, 1);

        for (auto const &[h, l] : cdis)
        {
            if (paths[k - l] != SIZE_MAX)
                min_path = min(min_path, h + paths[k - l]);
        }

        cdis.clear();
        find_path_lengths(v, k, c, w, 1);
    }

    for (size_t const i : modified)
        paths[i] = SIZE_MAX;
    modified.clear();

    for (auto const &[v, w] : g[c])
    {
        if (!visited[v])
        {
            decompose(v, k);
        }
    }
}

int best_path(int n, int k, int edges[][2], int length[])
{
    if (n == 1)
        return -1;

    g = vector<vector<pair<size_t, long>>>(n);
    for (size_t i = 0; i < n - 1; i++)
    {
        g[edges[i][0]].push_back({edges[i][1], length[i]});
        g[edges[i][1]].push_back({edges[i][0], length[i]});
    }

    subtr_size = vector<size_t>(n);
    visited = vector<bool>(n, 0);
    cdis = vector<pair<size_t, long>>(n);
    paths = vector<size_t>(k + 1, SIZE_MAX);

    decompose(0, k);

    if (min_path == SIZE_MAX)
        return -1;
    return min_path;
}

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:110:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     for (size_t i = 0; i < n - 1; i++)
      |                        ~~^~~~~~~

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