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

Текущий подход с DP по лесу правильный. Главная лишняя работа — take() заново вызывает combine() для каждого выбранного узла. Ниже восстановление использует уже сохранённые префиксные состояния и не пересчитывает knapsack.

Дополнительно:

• размеры DP ограничены реальным размером поддерева;
• блокировка недоступных зависимостей распространяется за O(n), без повторных проходов;
• std::unordered_map используется вместо std::map;
• один CURL-handle переиспользуется для всех запросов;
• порядок ответа формируется непосредственно при восстановлении.

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)),
          curl_(curl_easy_init()) {
        if (curl_ == nullptr) {
            throw std::runtime_error("curl_easy_init failed");
        }

        curl_easy_setopt(curl_, CURLOPT_WRITEFUNCTION, writeCallback);
        curl_easy_setopt(curl_, CURLOPT_NOSIGNAL, 1L);
        curl_easy_setopt(curl_, CURLOPT_FOLLOWLOCATION, 1L);
    }

    ~HttpClient() {
        if (curl_ != nullptr) {
            curl_easy_cleanup(curl_);
        }
    }

    json getJson(const std::string& path) {
        std::string response;
        const std::string url = baseUrl_ + path;

        curl_easy_setopt(curl_, CURLOPT_URL, url.c_str());
        curl_easy_setopt(curl_, CURLOPT_WRITEDATA, &response);

        const CURLcode result = curl_easy_perform(curl_);
        if (result != CURLE_OK) {
            throw std::runtime_error(curl_easy_strerror(result));
        }

        long status = 0;
        curl_easy_getinfo(curl_, CURLINFO_RESPONSE_CODE, &status);

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

        return json::parse(response);
    }

private:
    std::string baseUrl_;
    CURL* curl_;
};

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;
    }

    if (first > 0) {
        value.erase(0, first);
    }
}

// Объединяет два независимых леса.
// a[x] и b[y] — лучшие значения при выборе x и y штампов.
static std::vector<int> mergeDp(
    const std::vector<int>& a,
    const std::vector<int>& b,
    int limit
) {
    const int maxA = static_cast<int>(a.size()) - 1;
    const int maxB = static_cast<int>(b.size()) - 1;
    const int maxResult = std::min(limit, maxA + maxB);

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

    for (int x = 0; x <= maxA && x <= limit; ++x) {
        if (a[x] == NEG) {
            continue;
        }

        const int maxY = std::min(maxB, limit - x);

        for (int y = 0; y <= maxY; ++y) {
            if (b[y] == NEG) {
                continue;
            }

            result[x + y] = std::max(
                result[x + y],
                a[x] + b[y]
            );
        }
    }

    return result;
}

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

    // Здесь хранятся только выбранные штампы из детей.
    // Для самого vertex потребуется ещё одно место.
    std::vector<int> merged(1, 0);

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

    for (int child : nodes[vertex].children) {
        nodes[vertex].prefix.push_back(merged);
        merged = mergeDp(merged, nodes[child].dp, K - 1);
    }

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

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

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

        nodes[vertex].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>& treeRoots,
    const std::vector<std::vector<int>>& prefix,
    int takeCount,
    int targetValue,
    std::vector<int64>& answer
) {
    for (int i = static_cast<int>(treeRoots.size()) - 1;
         i >= 0;
         --i) {
        const int root = treeRoots[i];
        const std::vector<int>& previous = prefix[i];

        int chosenFromRoot = -1;

        const int maxFromRoot = std::min(
            takeCount,
            static_cast<int>(nodes[root].dp.size()) - 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);

    const int fromChildren = takeCount - 1;
    const int childrenValue =
        nodes[vertex].dp[takeCount] - nodes[vertex].rarity;

    restoreIndependentTrees(
        nodes[vertex].children,
        nodes[vertex].prefix,
        fromChildren,
        childrenValue,
        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);

        const json tour = client.getJson("/tour/" + tourId);

        const int64 startIsland = asId(tour.at("start_island"));
        K = static_cast<int>(asId(tour.at("max_stamps")));

        const json islandsJson =
            client.getJson("/islands?tour_id=" + tourId);

        std::unordered_map<int64, int> islandIndex;
        islandIndex.reserve(
            islandsJson.at("islands").size() * 2 + 1
        );

        for (const json& island : islandsJson.at("islands")) {
            const int64 id = asId(island);

            if (!islandIndex.count(id)) {
                const int index =
                    static_cast<int>(islandIndex.size());
                islandIndex.emplace(id, index);
            }
        }

        const int islandCount =
            static_cast<int>(islandIndex.size());

        std::vector<std::vector<int>> routes(islandCount);

        const json routesJson =
            client.getJson("/routes?tour_id=" + tourId);

        for (const json& route : routesJson.at("routes")) {
            const int64 fromId = asId(route.at("from"));
            const int64 toId = asId(route.at("to"));

            const auto fromIt = islandIndex.find(fromId);
            const auto toIt = islandIndex.find(toId);

            if (fromIt != islandIndex.end() &&
                toIt != islandIndex.end()) {
                routes[fromIt->second].push_back(toIt->second);
            }
        }

        std::vector<char> reachable(islandCount, false);
        std::vector<int> stack;

        const auto startIt = islandIndex.find(startIsland);

        if (startIt != islandIndex.end()) {
            reachable[startIt->second] = true;
            stack.push_back(startIt->second);
        }

        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);
                }
            }
        }

        const json stampsJson =
            client.getJson("/stamps?tour_id=" + tourId);

        const json& stamps = stampsJson.at("stamps");
        const int n = static_cast<int>(stamps.size());

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

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

        nodes.assign(n, StampNode{});

        std::vector<int64> stampIsland(n);
        std::vector<int64> requirementId(n);
        std::vector<char> hasRequirement(n, false);

        std::unordered_map<int64, int> stampIndex;
        stampIndex.reserve(n * 2 + 1);

        for (int i = 0; i < n; ++i) {
            const json& stamp = stamps[i];

            nodes[i].id = asId(stamp.at("stamp_id"));
            nodes[i].rarity = stamp.at("rarity").get<int>();
            stampIsland[i] = asId(stamp.at("island_id"));

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

            if (requirementsIt != stamp.end() &&
                requirementsIt->is_array() &&
                !requirementsIt->empty()) {
                hasRequirement[i] = true;
                requirementId[i] = asId((*requirementsIt)[0]);
            }

            stampIndex[nodes[i].id] = i;
        }

        std::vector<int> parent(n, -1);
        std::vector<std::vector<int>> dependencyChildren(n);
        std::vector<char> blocked(n, false);

        for (int i = 0; i < n; ++i) {
            const auto islandIt =
                islandIndex.find(stampIsland[i]);

            if (islandIt == islandIndex.end() ||
                !reachable[islandIt->second]) {
                blocked[i] = true;
            }

            if (hasRequirement[i]) {
                const auto requirementIt =
                    stampIndex.find(requirementId[i]);

                if (requirementIt == stampIndex.end()) {
                    blocked[i] = true;
                } else {
                    parent[i] = requirementIt->second;
                    dependencyChildren[parent[i]].push_back(i);
                }
            }
        }

        // Если штамп недоступен, все зависящие от него штампы
        // также недоступны.
        std::queue<int> blockedQueue;

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

        while (!blockedQueue.empty()) {
            const int vertex = blockedQueue.front();
            blockedQueue.pop();

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

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

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

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

        if (roots.empty()) {
            std::cout << 0 << '\n';
            curl_global_cleanup();
            return 0;
        }

        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);
        }

        int bestCount = 0;

        for (int count = 1;
             count < static_cast<int>(totalDp.size());
             ++count) {
            if (totalDp[count] > totalDp[bestCount]) {
                bestCount = count;
            }
        }

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

        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;
}

Сложность

Пусть n — количество штампов.

• достижимость островов: O(islands + routes);
• распространение недоступности: O(n);
• DP по лесу: O(n · k²);
• восстановление: O(n · k);
• память: O(n · k).

При максимальных ограничениях 420 · 90² ≈ 3.4 млн DP-переходов, что с большим запасом укладывается в лимит.

Главный тормоз текущего решения — бинарные подъёмы:

cpp
up.resize(lg * 2 * n);

При n = 10^6 это около 42 миллионов uint32_t, то есть примерно 168 МБ только для up. Кроме того, таблица целиком заполняется и многократно читается.

Её можно полностью убрать.

Идея

Для каждого интервала определим next[v] — следующий интервал, который выберет стандартный жадный алгоритм: среди всех интервалов, начинающихся не раньше окончания v, берём интервал с минимальным временем окончания.

У такого перехода:

• начало следующего интервала строго больше начала текущего;
• окончание следующего интервала строго больше окончания текущего;
• циклов нет.

Значит, переходы образуют лес. Развернём рёбра и обойдём этот лес DFS. На текущем пути от корня к вершине времена окончания строго убывают. Для исходной задачи i нужно найти количество последних вершин пути, чьи окончания не превосходят s[i] + T. Это один бинарный поиск по текущему пути.

Два периода хранятся только логически — массивы start и finish имеют размер n, а не 2n.

cpp
#include <cstdio>
#include <cstdint>
#include <limits>
#include <string>
#include <vector>

using namespace std;

class FastInput {
    static constexpr size_t BUFFER_SIZE = 1u << 20;

    char buffer[BUFFER_SIZE];
    size_t position = 0;
    size_t length = 0;

    inline char getChar() {
        if (position == length) {
            length = fread(buffer, 1, BUFFER_SIZE, stdin);
            position = 0;

            if (length == 0) {
                return 0;
            }
        }

        return buffer[position++];
    }

public:
    inline uint32_t nextUInt() {
        char c = getChar();

        while (c < '0' || c > '9') {
            c = getChar();
        }

        uint32_t value = 0;

        do {
            value = value * 10u + static_cast<uint32_t>(c - '0');
            c = getChar();
        } while (c >= '0' && c <= '9');

        return value;
    }
};

static inline uint32_t lowerBound(
    const vector<uint32_t>& values,
    uint32_t target
) {
    uint32_t left = 0;
    uint32_t right = static_cast<uint32_t>(values.size());

    while (left < right) {
        const uint32_t middle = left + ((right - left) >> 1);

        if (values[middle] < target) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }

    return left;
}

int main() {
    FastInput input;

    const uint32_t testCount = input.nextUInt();

    string output;
    output.reserve(static_cast<size_t>(testCount) * 8u);

    vector<uint32_t> start;
    vector<uint32_t> finish;

    // Сначала используется как массив суффиксных минимумов,
    // затем переиспользуется как стек DFS.
    vector<uint32_t> work;

    // Обратный лес переходов в формате списков смежности.
    vector<uint32_t> head;
    vector<uint32_t> sibling;

    constexpr uint32_t NIL =
        numeric_limits<uint32_t>::max();

    for (uint32_t test = 0; test < testCount; ++test) {
        const uint32_t n = input.nextUInt();
        const uint32_t period = input.nextUInt();
        const uint32_t vertexCount = n * 2u;

        start.resize(n);
        finish.resize(n);

        for (uint32_t i = 0; i < n; ++i) {
            const uint32_t s = input.nextUInt();
            const uint32_t d = input.nextUInt();

            start[i] = s;
            finish[i] = s + d;
        }

        /*
         * work[i] — индекс интервала с минимальным finish
         * среди интервалов [i, n).
         *
         * При равенстве выбираем меньший индекс.
         */
        work.resize(n + 1u);
        work[n] = NIL;

        for (uint32_t i = n; i-- > 0;) {
            const uint32_t rightBest = work[i + 1u];

            if (rightBest == NIL ||
                finish[i] <= finish[rightBest]) {
                work[i] = i;
            } else {
                work[i] = rightBest;
            }
        }

        const uint32_t globalBest = work[0];

        /*
         * Вершины:
         *   [0, n)   — интервалы первого периода;
         *   [n, 2n)  — интервалы второго периода.
         *
         * vertexCount — виртуальный корень для вершин,
         * у которых нет следующего интервала.
         */
        head.assign(vertexCount + 1u, NIL);
        sibling.resize(vertexCount);

        auto addChild = [&](uint32_t parent, uint32_t child) {
            sibling[child] = head[parent];
            head[parent] = child;
        };

        for (uint32_t i = 0; i < n; ++i) {
            const uint32_t end = finish[i];

            uint32_t nextFirstCopy = vertexCount;
            uint32_t nextSecondCopy = vertexCount;

            if (end < period) {
                /*
                 * Ищем первый старт >= end.
                 *
                 * Для первой копии есть два вида кандидатов:
                 * 1. суффикс первого периода;
                 * 2. любой интервал второго периода.
                 */
                const uint32_t first =
                    lowerBound(start, end);

                const uint32_t bestSuffix = work[first];

                if (bestSuffix != NIL &&
                    finish[bestSuffix] <=
                        finish[globalBest] + period) {
                    nextFirstCopy = bestSuffix;
                } else {
                    nextFirstCopy = globalBest + n;
                }

                /*
                 * После второй копии доступны только интервалы
                 * того же, второго периода.
                 */
                if (bestSuffix != NIL) {
                    nextSecondCopy = bestSuffix + n;
                }
            } else {
                /*
                 * Текущий интервал заканчивается уже во втором
                 * периоде. Следующий интервал может быть только
                 * во второй копии.
                 */
                const uint32_t first =
                    lowerBound(start, end - period);

                const uint32_t bestSuffix = work[first];

                if (bestSuffix != NIL) {
                    nextFirstCopy = bestSuffix + n;
                }

                // Для второй копии потребовался бы третий период,
                // который для рассматриваемого окна уже не нужен.
            }

            addChild(nextFirstCopy, i);
            addChild(nextSecondCopy, i + n);
        }

        /*
         * Суффиксные минимумы больше не нужны.
         * Переиспользуем их память под текущий путь DFS.
         */
        work.clear();
        work.reserve(vertexCount);

        auto& path = work;

        uint32_t answer = 1;

        auto enterVertex = [&](uint32_t vertex) {
            path.push_back(vertex);

            /*
             * Ответ нужен только для интервалов исходного периода:
             * именно их мы рассматриваем как первый выбранный
             * интервал на окружности.
             */
            if (vertex >= n) {
                return;
            }

            const uint32_t limit = start[vertex] + period;

            /*
             * На пути root -> vertex окончания строго убывают.
             * Ищем первый элемент с end <= limit.
             */
            uint32_t left = 0;
            uint32_t right =
                static_cast<uint32_t>(path.size());

            while (left < right) {
                const uint32_t middle =
                    left + ((right - left) >> 1);

                const uint32_t pathVertex = path[middle];
                const uint32_t baseIndex =
                    pathVertex < n
                        ? pathVertex
                        : pathVertex - n;

                /*
                 * Максимум:
                 * finish < 2 * 10^9,
                 * finish + period < 3 * 10^9,
                 * что помещается в uint32_t.
                 */
                const uint32_t endTime =
                    finish[baseIndex] +
                    (pathVertex >= n ? period : 0u);

                if (endTime > limit) {
                    left = middle + 1;
                } else {
                    right = middle;
                }
            }

            const uint32_t count =
                static_cast<uint32_t>(path.size()) - left;

            if (count > answer) {
                answer = count;
            }
        };

        /*
         * Итеративный DFS без отдельного массива visited
         * и без событий входа/выхода.
         *
         * head[v] используется как изменяемый указатель
         * на следующего необработанного ребёнка.
         */
        while (head[vertexCount] != NIL) {
            const uint32_t root = head[vertexCount];
            head[vertexCount] = sibling[root];

            enterVertex(root);

            while (!path.empty()) {
                const uint32_t vertex = path.back();
                const uint32_t child = head[vertex];

                if (child == NIL) {
                    path.pop_back();
                } else {
                    head[vertex] = sibling[child];
                    enterVertex(child);
                }
            }
        }

        char digits[16];
        int length = 0;

        do {
            digits[length++] =
                static_cast<char>('0' + answer % 10u);
            answer /= 10u;
        } while (answer != 0);

        while (length > 0) {
            output.push_back(digits[--length]);
        }

        output.push_back('\n');
    }

    fwrite(output.data(), 1, output.size(), stdout);
    return 0;
}