Submission #1218437

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218437		asturnox	Tropical Garden (IOI11_garden)	C++20	69 / 100	5093 ms	47064 KiB

garden

#include <iostream>
#include <iterator>
#include <memory>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

void answer(int X);

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
    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_walk = node_edges[walk][0];
        if (node_edges[walk].size() == 2 && next_walk == prev_walk) {
            next_walk = node_edges[walk][1];
        }
        return next_walk;
    };

    map <pair<int,int>, int> state_to_cycle_start_pos;
    map <pair<int,int>, int> state_to_path_pos;
    map <pair<int,int>, shared_ptr<deque<pair<int,int>>>> state_to_path_with_cycle;

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

        int prev_walk = node;
        int walk = do_walk(prev_walk, -1);
        int next_walk = do_walk(walk, prev_walk);

        while (g > 0) {
            --g;
            pair<int,int> state = {walk, next_walk};

            // Cache hit: fast-forward through cycle
            if (state_to_path_pos.count(state)) {
                int path_pos = state_to_path_pos[state];
                int cycle_start = state_to_cycle_start_pos[state];
                auto cyc_path = state_to_path_with_cycle[state];
                int cycle_size = int(cyc_path->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 (*cyc_path)[path_pos + g].first == P;
                }

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

            // First time in this state
            if (visited.insert(state).second) {
                path->push_back(state);
                int prev = walk;
                walk = do_walk(walk, prev_walk);
                if (prev == walk) {
                    return walk == P;
                }
                prev_walk = prev;
                next_walk = do_walk(walk, prev_walk);
            }
            // Found a cycle
            else {
                auto it = find(path->begin(), path->end(), state);
                int cycle_start = int(distance(path->begin(), it));
                for (int i = 0; i < (int)path->size(); ++i) {
                    auto s = (*path)[i];
                    state_to_path_pos[s] = i;
                    state_to_cycle_start_pos[s] = cycle_start;
                    state_to_path_with_cycle[s] = path;
                }
                int cycle_len = int(path->size()) - cycle_start;
                return (*path)[cycle_start + (g % cycle_len)].first == P;
            }
        }

        return path->back().first == P;
    };

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

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