제출 #684254

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

race

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

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

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

    int64_t 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, INT_MIN});
                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);
            }
            for (auto const &[length, num_edges] : s[v])
            {
                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, INT_MIN});
    if (it != s[u].end() && it->first + c[u].first == k)
        min_edges_num = min(min_edges_num, it->second + c[u].second);
    s[u].emplace(-c[u].first, -c[u].second);
}

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

    for (int64_t 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;
}

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

race.cpp: In function 'void find_best(int64_t, int64_t, int64_t)':
race.cpp:25:29: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long int, long int> >::size_type' {aka 'long unsigned int'} and 'int64_t' {aka 'long 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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57