Submission #684235

#	Time	Username	Problem	Language	Result	Execution time	Memory
684235		finn__	Race (IOI11_race)	C++17	0 / 100	1 ms	340 KiB

race

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

vector<set<pair<int, int>>> s;
vector<pair<int, int>> c;
vector<vector<pair<int, int>>> g;
int min_edges_num = INT_MAX;

void find_best(int u, int p, int k)
{
    if (g[u].size() == 1 && g[u].front().first == p)
    {
        s[u].emplace(0, 0);
        c[u] = {0, 0};
        return;
    }

    int max_v, max_size = 0, max_w;

    for (auto const &[v, w] : g[u])
        if (v != p)
        {
            find_best(v, u, k);
            if (s[v].size() > max_size)
                max_v = v, max_size = s[v].size(), max_w = w;
        }

    swap(s[u], s[max_v]);
    swap(c[u], c[max_v]);
    c[u].first += max_w;
    c[u].second++;

    for (auto const &[v, w] : g[u])
        if (v != p && v != max_v)
            for (auto const &[length, num_edges] : s[v])
            {
                auto it = s[u].lower_bound({k - (length + w + c[v].first) - c[u].first, 0});
                if (it != s[u].end() && it->first + c[u].first + length + w + c[v].first == k)
                    min_edges_num = min(min_edges_num, it->second + c[u].second + num_edges + 1 + c[v].second - c[u].second);

                s[u].emplace(length + w + c[v].first - c[u].first,
                             num_edges + 1 + c[v].second - c[u].second);
            }

    auto it = s[u].lower_bound({k - c[u].first, 0});
    if (it != s[u].end() && it->first + c[u].first == k)
        min_edges_num = min(min_edges_num, it->second + c[u].second);
}

int best_path(int N, int K, int H[][2], int L[])
{
    g = vector<vector<pair<int, int>>>(N);
    s = vector<set<pair<int, int>>>(N);
    c = vector<pair<int, int>>(N);

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

    find_best(0, -1, K);
    return min_edges_num == INT_MAX ? -1 : min_edges_num;
}

Compilation message (stderr)

race.cpp: In function 'void find_best(int, int, int)':
race.cpp:25:29: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |             if (s[v].size() > max_size)
      |                 ~~~~~~~~~~~~^~~~~~~~~~
race.cpp:31:16: warning: 'max_w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     c[u].first += max_w;
race.cpp:35:20: warning: 'max_v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |         if (v != p && v != max_v)
      |             ~~~~~~~^~~~~~~~~~~~~

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