Submission #639476

#	Time	Username	Problem	Language	Result	Execution time	Memory
639476		finn__	Race (IOI11_race)	C++17	21 / 100	3061 ms	50792 KiB

race

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

using namespace std;

struct node
{
    size_t u, s; // id, number of edges to the centroid.
};

vector<map<size_t, long>> g;

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

unordered_map<size_t, pair<node, node>> paths;
vector<pair<node, long>> cdis;
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 p = -1, size_t l = 0, size_t h = 0)
{
    auto it = paths.find(l);

    if (it == paths.end())
        paths[l] = make_pair((node){u, h}, (node){0, SIZE_MAX});
    else
    {
        if (h < it->second.first.s)
        {
            it->second.second = it->second.first;
            it->second.first = {u, h};
        }
        else if (h < it->second.second.s)
        {
            it->second.second = {u, h};
        }
    }

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

void find_cdis(size_t u, size_t p = -1, size_t l = 0, size_t h = 0)
{
    cdis.push_back(make_pair((node){u, h}, l));

    for (auto const [v, w] : g[u])
        if (!visited[v] && v != p)
            find_cdis(v, 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] = make_pair((node){c, 0}, (node){0, SIZE_MAX});

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

        for (auto const &[x, l] : cdis)
        {
            auto it = paths.find(k - l);

            if (it != paths.end())
            {
                if (it->second.first.u == x.u)
                {
                    if (it->second.second.s != SIZE_MAX)
                        min_path = min(min_path, it->second.second.s + x.s);
                }
                else
                {
                    min_path = min(min_path, it->second.first.s + x.s);
                }
            }
        }

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

    paths.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<map<size_t, long>>(n);
    for (size_t i = 0; i < n - 1; i++)
    {
        g[edges[i][0]][edges[i][1]] = g[edges[i][1]][edges[i][0]] = length[i];
    }

    subtr_size = vector<size_t>(n);
    visited = vector<bool>(n, 0);
    cdis = vector<pair<node, long>>(n);

    decompose(0, k);

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

Compilation message (stderr)

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

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