Кодерун путешествует по архипелагу и собирает ре...

Главный bottleneck — четыре последовательных HTTP-запроса. По времени 573–579 мс видно, что DP почти не влияет на результат.

Оптимизации:

1. /tour, /routes и /stamps запрашиваются одновременно через curl_multi.
2. Запрос /islands удалён: все острова, важные для решения, встречаются как стартовый остров, конец переправы или остров штампа.
3. Так как rarity >= 1, оптимальный ответ всегда содержит ровно min(max_stamps, число доступных штампов) элементов.
4. DP ограничивается актуальным размером поддеревьев и значением K.

Сетевая часть теперь занимает примерно максимум из задержек трёх запросов вместо их суммы.

cpp
#include <algorithm>
#include <cctype>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include <curl/curl.h>
#include "json.hpp"

using json = nlohmann::json;
using int64 = long long;

static constexpr int NEG = -1'000'000'000;

static int K;

struct StampNode {
    int64 id = 0;
    int rarity = 0;

    std::vector<int> children;

    // dp[x] — максимум при выборе x штампов из поддерева.
    // При x > 0 текущая вершина обязательно выбрана.
    std::vector<int> dp;

    // prefix[i] — результат объединения детей [0, i).
    std::vector<std::vector<int>> prefix;
};

static std::vector<StampNode> nodes;

static size_t writeCallback(
    char* ptr,
    size_t size,
    size_t nmemb,
    void* userdata
) {
    auto& output = *static_cast<std::string*>(userdata);
    output.append(ptr, size * nmemb);
    return size * nmemb;
}

class HttpClient {
public:
    explicit HttpClient(std::string baseUrl)
        : baseUrl_(std::move(baseUrl)) {
    }

    std::vector<json> getJsonBatch(
        const std::vector<std::string>& paths
    ) const {
        struct Request {
            CURL* easy = nullptr;
            bool added = false;
            bool finished = false;

            CURLcode result = CURLE_FAILED_INIT;

            std::string url;
            std::string body;
        };

        CURLM* multi = curl_multi_init();

        if (multi == nullptr) {
            throw std::runtime_error("curl_multi_init failed");
        }

        std::vector<Request> requests(paths.size());

        auto cleanup = [&]() {
            if (multi == nullptr) {
                return;
            }

            for (Request& request : requests) {
                if (request.easy == nullptr) {
                    continue;
                }

                if (request.added) {
                    curl_multi_remove_handle(multi, request.easy);
                    request.added = false;
                }

                curl_easy_cleanup(request.easy);
                request.easy = nullptr;
            }

            curl_multi_cleanup(multi);
            multi = nullptr;
        };

        try {
            curl_multi_setopt(
                multi,
                CURLMOPT_MAX_HOST_CONNECTIONS,
                static_cast<long>(paths.size())
            );

            for (size_t i = 0; i < paths.size(); ++i) {
                Request& request = requests[i];

                request.url = baseUrl_ + paths[i];
                request.easy = curl_easy_init();

                if (request.easy == nullptr) {
                    throw std::runtime_error("curl_easy_init failed");
                }

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_URL,
                    request.url.c_str()
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_WRITEFUNCTION,
                    writeCallback
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_WRITEDATA,
                    &request.body
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_PRIVATE,
                    &request
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_NOSIGNAL,
                    1L
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_FOLLOWLOCATION,
                    1L
                );

                curl_easy_setopt(
                    request.easy,
                    CURLOPT_TCP_NODELAY,
                    1L
                );

                const CURLMcode addResult =
                    curl_multi_add_handle(multi, request.easy);

                if (addResult != CURLM_OK) {
                    throw std::runtime_error(
                        curl_multi_strerror(addResult)
                    );
                }

                request.added = true;
            }

            int running = 0;

            CURLMcode multiResult =
                curl_multi_perform(multi, &running);

            if (multiResult != CURLM_OK) {
                throw std::runtime_error(
                    curl_multi_strerror(multiResult)
                );
            }

            while (running > 0) {
                int descriptorCount = 0;

                multiResult = curl_multi_wait(
                    multi,
                    nullptr,
                    0,
                    1000,
                    &descriptorCount
                );

                if (multiResult != CURLM_OK) {
                    throw std::runtime_error(
                        curl_multi_strerror(multiResult)
                    );
                }

                multiResult =
                    curl_multi_perform(multi, &running);

                if (multiResult != CURLM_OK) {
                    throw std::runtime_error(
                        curl_multi_strerror(multiResult)
                    );
                }
            }

            int messagesLeft = 0;

            while (CURLMsg* message =
                       curl_multi_info_read(
                           multi,
                           &messagesLeft
                       )) {
                if (message->msg != CURLMSG_DONE) {
                    continue;
                }

                void* privateData = nullptr;

                curl_easy_getinfo(
                    message->easy_handle,
                    CURLINFO_PRIVATE,
                    &privateData
                );

                auto* request =
                    static_cast<Request*>(privateData);

                if (request == nullptr) {
                    throw std::runtime_error(
                        "Missing CURL request data"
                    );
                }

                request->finished = true;
                request->result = message->data.result;
            }

            for (Request& request : requests) {
                if (!request.finished) {
                    throw std::runtime_error(
                        "HTTP request was not completed"
                    );
                }

                if (request.result != CURLE_OK) {
                    throw std::runtime_error(
                        curl_easy_strerror(request.result)
                    );
                }

                long status = 0;

                curl_easy_getinfo(
                    request.easy,
                    CURLINFO_RESPONSE_CODE,
                    &status
                );

                if (status < 200 || status >= 300) {
                    throw std::runtime_error(
                        "HTTP error: " +
                        std::to_string(status)
                    );
                }
            }

            std::vector<json> result;
            result.reserve(requests.size());

            for (const Request& request : requests) {
                result.push_back(
                    json::parse(request.body)
                );
            }

            cleanup();
            return result;
        } catch (...) {
            cleanup();
            throw;
        }
    }

private:
    std::string baseUrl_;
};

static int64 asId(const json& value) {
    if (value.is_string()) {
        return std::stoll(
            value.get<std::string>()
        );
    }

    return value.get<int64>();
}

static void trim(std::string& value) {
    while (!value.empty() &&
           std::isspace(
               static_cast<unsigned char>(value.back())
           )) {
        value.pop_back();
    }

    size_t first = 0;

    while (first < value.size() &&
           std::isspace(
               static_cast<unsigned char>(value[first])
           )) {
        ++first;
    }

    value.erase(0, first);
}

static std::vector<int> mergeDp(
    const std::vector<int>& left,
    const std::vector<int>& right,
    int limit
) {
    const int maxLeft = std::min(
        limit,
        static_cast<int>(left.size()) - 1
    );

    const int maxRight = std::min(
        limit,
        static_cast<int>(right.size()) - 1
    );

    const int maxResult = std::min(
        limit,
        maxLeft + maxRight
    );

    std::vector<int> result(
        maxResult + 1,
        NEG
    );

    for (int leftCount = 0;
         leftCount <= maxLeft;
         ++leftCount) {
        if (left[leftCount] == NEG) {
            continue;
        }

        const int maxRightCount = std::min(
            maxRight,
            limit - leftCount
        );

        for (int rightCount = 0;
             rightCount <= maxRightCount;
             ++rightCount) {
            if (right[rightCount] == NEG) {
                continue;
            }

            result[leftCount + rightCount] =
                std::max(
                    result[leftCount + rightCount],
                    left[leftCount] +
                        right[rightCount]
                );
        }
    }

    return result;
}

static void buildDp(int vertex) {
    for (int child : nodes[vertex].children) {
        buildDp(child);
    }

    // Количество выбранных штампов только из детей.
    std::vector<int> merged(1, 0);

    auto& prefix = nodes[vertex].prefix;

    prefix.clear();
    prefix.reserve(
        nodes[vertex].children.size()
    );

    for (int child : nodes[vertex].children) {
        prefix.push_back(merged);

        // Одно место резервируется для vertex.
        merged = mergeDp(
            merged,
            nodes[child].dp,
            K - 1
        );
    }

    const int maxTake = std::min(
        K,
        static_cast<int>(merged.size())
    );

    auto& dp = nodes[vertex].dp;

    dp.assign(maxTake + 1, NEG);
    dp[0] = 0;

    for (int fromChildren = 0;
         fromChildren <
             static_cast<int>(merged.size()) &&
         fromChildren + 1 <= K;
         ++fromChildren) {
        if (merged[fromChildren] == NEG) {
            continue;
        }

        dp[fromChildren + 1] =
            nodes[vertex].rarity +
            merged[fromChildren];
    }
}

static void restoreNode(
    int vertex,
    int takeCount,
    std::vector<int64>& answer
);

static void restoreIndependentTrees(
    const std::vector<int>& roots,
    const std::vector<std::vector<int>>& prefix,
    int takeCount,
    int targetValue,
    std::vector<int64>& answer
) {
    for (int i = static_cast<int>(roots.size()) - 1;
         i >= 0;
         --i) {
        const int root = roots[i];
        const std::vector<int>& previous = prefix[i];

        const int maxFromRoot = std::min(
            takeCount,
            static_cast<int>(
                nodes[root].dp.size()
            ) - 1
        );

        int chosenFromRoot = -1;

        for (int fromRoot = 0;
             fromRoot <= maxFromRoot;
             ++fromRoot) {
            const int fromPrevious =
                takeCount - fromRoot;

            if (fromPrevious >=
                static_cast<int>(previous.size())) {
                continue;
            }

            if (previous[fromPrevious] == NEG ||
                nodes[root].dp[fromRoot] == NEG) {
                continue;
            }

            if (previous[fromPrevious] +
                    nodes[root].dp[fromRoot] ==
                targetValue) {
                chosenFromRoot = fromRoot;
                break;
            }
        }

        if (chosenFromRoot < 0) {
            throw std::runtime_error(
                "DP reconstruction failed"
            );
        }

        takeCount -= chosenFromRoot;
        targetValue = previous[takeCount];

        if (chosenFromRoot > 0) {
            restoreNode(
                root,
                chosenFromRoot,
                answer
            );
        }
    }
}

static void restoreNode(
    int vertex,
    int takeCount,
    std::vector<int64>& answer
) {
    // Требование выводится раньше зависимых штампов.
    answer.push_back(nodes[vertex].id);

    restoreIndependentTrees(
        nodes[vertex].children,
        nodes[vertex].prefix,
        takeCount - 1,
        nodes[vertex].dp[takeCount] -
            nodes[vertex].rarity,
        answer
    );
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string baseUrl;
    std::string tourId;

    std::getline(std::cin, baseUrl);
    std::getline(std::cin, tourId);

    trim(baseUrl);
    trim(tourId);

    if (curl_global_init(CURL_GLOBAL_DEFAULT) !=
        CURLE_OK) {
        std::cout << 0 << '\n';
        return 0;
    }

    try {
        HttpClient client(baseUrl);

        // Все запросы независимы: tour_id уже прочитан
        // из стандартного ввода.
        const std::vector<json> responses =
            client.getJsonBatch({
                "/tour/" + tourId,
                "/routes?tour_id=" + tourId,
                "/stamps?tour_id=" + tourId
            });

        const json& tour = responses[0];
        const json& routesJson = responses[1];
        const json& stampsJson = responses[2];

        const int64 startIsland =
            asId(tour.at("start_island"));

        K = static_cast<int>(
            asId(tour.at("max_stamps"))
        );

        struct RawStamp {
            int64 id = 0;
            int64 island = 0;
            int rarity = 0;

            bool hasRequirement = false;
            int64 requirement = 0;
        };

        const json& stampArray =
            stampsJson.at("stamps");

        const int stampCount =
            static_cast<int>(stampArray.size());

        K = std::min(K, stampCount);

        if (K <= 0 || stampCount == 0) {
            std::cout << 0 << '\n';
            curl_global_cleanup();
            return 0;
        }

        std::vector<RawStamp> rawStamps;
        rawStamps.reserve(stampCount);

        for (const json& stamp : stampArray) {
            RawStamp raw;

            raw.id = asId(stamp.at("stamp_id"));
            raw.island =
                asId(stamp.at("island_id"));
            raw.rarity =
                stamp.at("rarity").get<int>();

            const auto requiresIt =
                stamp.find("requires");

            if (requiresIt != stamp.end() &&
                requiresIt->is_array() &&
                !requiresIt->empty()) {
                raw.hasRequirement = true;
                raw.requirement =
                    asId((*requiresIt)[0]);
            }

            rawStamps.push_back(raw);
        }

        std::vector<std::pair<int64, int64>>
            rawRoutes;

        rawRoutes.reserve(
            routesJson.at("routes").size()
        );

        for (const json& route :
             routesJson.at("routes")) {
            rawRoutes.emplace_back(
                asId(route.at("from")),
                asId(route.at("to"))
            );
        }

        // Отдельный GET /islands не требуется.
        // Все значимые острова встречаются в startIsland,
        // routes или stamps.
        std::unordered_map<int64, int> islandIndex;

        islandIndex.reserve(
            rawRoutes.size() * 2 +
            rawStamps.size() +
            1
        );

        std::vector<std::vector<int>> routes;

        auto getIslandIndex = [&](int64 island) {
            const auto it =
                islandIndex.find(island);

            if (it != islandIndex.end()) {
                return it->second;
            }

            const int index =
                static_cast<int>(routes.size());

            islandIndex.emplace(island, index);
            routes.emplace_back();

            return index;
        };

        const int startIndex =
            getIslandIndex(startIsland);

        for (const auto& [from, to] : rawRoutes) {
            const int fromIndex =
                getIslandIndex(from);

            const int toIndex =
                getIslandIndex(to);

            routes[fromIndex].push_back(toIndex);
        }

        for (const RawStamp& stamp : rawStamps) {
            getIslandIndex(stamp.island);
        }

        std::vector<char> reachable(
            routes.size(),
            false
        );

        std::vector<int> stack;
        stack.reserve(routes.size());

        reachable[startIndex] = true;
        stack.push_back(startIndex);

        while (!stack.empty()) {
            const int vertex = stack.back();
            stack.pop_back();

            for (int next : routes[vertex]) {
                if (!reachable[next]) {
                    reachable[next] = true;
                    stack.push_back(next);
                }
            }
        }

        nodes.assign(
            stampCount,
            StampNode{}
        );

        std::unordered_map<int64, int> stampIndex;

        stampIndex.reserve(
            stampCount * 2 + 1
        );

        for (int i = 0; i < stampCount; ++i) {
            nodes[i].id = rawStamps[i].id;
            nodes[i].rarity =
                rawStamps[i].rarity;

            stampIndex.emplace(
                rawStamps[i].id,
                i
            );
        }

        std::vector<int> parent(
            stampCount,
            -1
        );

        std::vector<std::vector<int>>
            dependencyChildren(stampCount);

        std::vector<char> blocked(
            stampCount,
            false
        );

        for (int i = 0; i < stampCount; ++i) {
            const int island =
                islandIndex.at(
                    rawStamps[i].island
                );

            if (!reachable[island]) {
                blocked[i] = true;
            }

            if (!rawStamps[i].hasRequirement) {
                continue;
            }

            const auto requirementIt =
                stampIndex.find(
                    rawStamps[i].requirement
                );

            if (requirementIt ==
                stampIndex.end()) {
                blocked[i] = true;
                continue;
            }

            parent[i] = requirementIt->second;

            dependencyChildren[parent[i]]
                .push_back(i);
        }

        // Недоступность распространяется вниз
        // по дереву зависимостей.
        std::vector<int> blockedQueue;
        blockedQueue.reserve(stampCount);

        for (int i = 0; i < stampCount; ++i) {
            if (blocked[i]) {
                blockedQueue.push_back(i);
            }
        }

        for (size_t head = 0;
             head < blockedQueue.size();
             ++head) {
            const int vertex =
                blockedQueue[head];

            for (int child :
                 dependencyChildren[vertex]) {
                if (!blocked[child]) {
                    blocked[child] = true;
                    blockedQueue.push_back(child);
                }
            }
        }

        std::vector<int> roots;
        roots.reserve(stampCount);

        int availableCount = 0;

        for (int i = 0; i < stampCount; ++i) {
            if (blocked[i]) {
                continue;
            }

            ++availableCount;

            if (parent[i] == -1) {
                roots.push_back(i);
            } else {
                nodes[parent[i]].children
                    .push_back(i);
            }
        }

        if (availableCount == 0) {
            std::cout << 0 << '\n';
            curl_global_cleanup();
            return 0;
        }

        K = std::min(K, availableCount);

        for (int root : roots) {
            buildDp(root);
        }

        std::vector<int> totalDp(1, 0);

        std::vector<std::vector<int>>
            rootPrefix;

        rootPrefix.reserve(roots.size());

        for (int root : roots) {
            rootPrefix.push_back(totalDp);

            totalDp = mergeDp(
                totalDp,
                nodes[root].dp,
                K
            );
        }

        // Все редкости положительны, поэтому оптимум
        // использует максимально допустимое число штампов.
        const int bestCount = K;

        std::vector<int64> answer;
        answer.reserve(bestCount);

        restoreIndependentTrees(
            roots,
            rootPrefix,
            bestCount,
            totalDp[bestCount],
            answer
        );

        std::cout << answer.size() << '\n';

        for (size_t i = 0;
             i < answer.size();
             ++i) {
            if (i != 0) {
                std::cout << ' ';
            }

            std::cout << answer[i];
        }

        std::cout << '\n';
    } catch (...) {
        std::cout << 0 << '\n';
    }

    curl_global_cleanup();
    return 0;
}

Итоговая сложность вычислительной части:

• достижимость островов: O(islands + routes);
• обработка зависимостей: O(stamps);
• tree knapsack: до O(stamps · K²);
• память: O(stamps · K).

При данных ограничениях вычислительная часть обычно занимает доли миллисекунды, поэтому параллельные запросы дают основное ускорение.