제출 #639493

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

race

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

using namespace std;

vector<vector<pair<unsigned, int>>> g;

vector<unsigned> subtr_size;
vector<bool> visited;

vector<unsigned> paths;
vector<pair<unsigned, int>> cdis;
vector<unsigned> modified;
unsigned min_path = UINT_MAX;

unsigned get_size(unsigned u, unsigned p)
{
    unsigned 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;
}

unsigned find_centroid(unsigned u, unsigned p, unsigned 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(unsigned u, unsigned k, unsigned p = -1, unsigned l = 0, unsigned 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(unsigned u, unsigned k, unsigned p = -1, unsigned l = 0, unsigned 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(unsigned u, unsigned k)
{
    unsigned n = get_size(u, -1);
    unsigned 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] != UINT_MAX)
                min_path = min(min_path, h + paths[k - l]);
        }

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

    for (unsigned const i : modified)
        paths[i] = UINT_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<unsigned, int>>>(n);
    for (unsigned 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<unsigned>(n);
    visited = vector<bool>(n, 0);
    cdis = vector<pair<unsigned, int>>(n);
    paths = vector<unsigned>(k + 1, UINT_MAX);

    decompose(0, k);

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

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

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

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