Submission #1218438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218438		asturnox	Tropical Garden (IOI11_garden)	C++20	49 / 100	5094 ms	36596 KiB

garden

#include <iostream>
#include <iterator>
#include <memory>
#include <vector>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

using namespace std;
using StateKey = uint64_t;

inline StateKey pack_state(int walk, int prev) {
    return (uint64_t(walk) << 32) | uint32_t(prev);
}

void answer(int X);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    // Build adjacency lists, but only keep up to 2 edges per node
    vector<vector<int>> node_edges(N + 1);
    for (int idx = 0; idx < M; ++idx) {
        int i = R[idx][0];
        int j = R[idx][1];
        if (node_edges[i].size() < 2) node_edges[i].push_back(j);
        if (node_edges[j].size() < 2) node_edges[j].push_back(i);
    }

    auto do_walk = [&](int walk, int prev_walk) {
        if (node_edges[walk].empty()) return walk;
        int next = node_edges[walk][0];
        if (node_edges[walk].size() == 2 && next == prev_walk)
            next = node_edges[walk][1];
        return next;
    };

    // Switch to hash-based caches for O(1) amortized lookups
    unordered_map<StateKey, int> state_to_path_pos;
    unordered_map<StateKey, int> state_to_cycle_start_pos;
    unordered_map<StateKey, shared_ptr<deque<pair<int,int>>>> state_to_path_with_cycle;
    unordered_set<StateKey> visited;

    // Reserve to avoid rehash
    state_to_path_pos.reserve(2 * N);
    state_to_cycle_start_pos.reserve(2 * N);
    state_to_path_with_cycle.reserve(2 * N);
    visited.reserve(2 * N);

    auto can_from_node = [&](int node, int g) {
        auto path = make_shared<deque<pair<int,int>>>();
        visited.clear();

        int prev = node;
        int walk = do_walk(prev, -1);
        int next = do_walk(walk, prev);

        while (g > 0) {
            --g;
            StateKey key = pack_state(walk, next);

            // Cache hit: compute directly without extra loops
            if (state_to_path_pos.count(key)) {
                int path_pos = state_to_path_pos[key];
                int cycle_start = state_to_cycle_start_pos[key];
                auto path_with_cycle = state_to_path_with_cycle[key];
                int cycle_len = path_with_cycle->size() - cycle_start;

                int g_rem;
                if (path_pos >= cycle_start) {
                    g_rem = g + (path_pos - cycle_start);
                } else if (path_pos + g >= cycle_start) {
                    g_rem = g - (cycle_start - path_pos);
                } else {
                    return (*path_with_cycle)[path_pos + g].first == P;
                }

                int idx = cycle_start + (g_rem % cycle_len);
                return (*path_with_cycle)[idx].first == P;
            }

            // First time seeing this state
            if (!visited.count(key)) {
                visited.insert(key);
                path->emplace_back(walk, next);

                int temp = walk;
                walk = do_walk(walk, prev);
                if (temp == walk) return walk == P;

                prev = temp;
                next = do_walk(walk, prev);
            } else {
                // Found a cycle: cache path positions and cycle start
                auto it = find(path->begin(), path->end(), make_pair(walk, next));
                int cycle_start = distance(path->begin(), it);

                for (int i = 0; i < (int)path->size(); ++i) {
                    StateKey k = pack_state(path->at(i).first, path->at(i).second);
                    state_to_path_pos[k] = i;
                    state_to_cycle_start_pos[k] = cycle_start;
                    state_to_path_with_cycle[k] = path;
                }

                int cycle_len = path->size() - cycle_start;
                int idx = cycle_start + (g % cycle_len);
                return (*path)[idx].first == P;
            }
        }

        // No more steps: check final node
        return path->back().first == P;
    };

    for (int i = 0; i < Q; ++i) {
        int g_val = G[i];
        int count = 0;
        for (int node = 0; node < N; ++node) {
            if (can_from_node(node, g_val)) count++;
        }
        answer(count);
    }
}

• Subtask 1: 49 / 49
• Subtask 2: 0 / 20
• Subtask 3: 0 / 31