Submission #1218053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218053		asturnox	Tropical Garden (IOI11_garden)	C++20	49 / 100	5091 ms	47076 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[]) {
    // 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);
        }
    }

    // Walk function: choose the neighbor that's not the one we came from
    auto do_walk = [&](int walk, int prev_walk) {
        if (node_edges[walk].empty()) {
            // No neighbors, same
            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>, std::shared_ptr< deque<pair<int, int>>> > state_to_path_with_cycle;

    // Can we, starting from `node`, after g steps end up at node P?
    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);  // uses default prev_walk = -1

        while (g > 0) {
            g--;

            pair<int,int> state = make_pair(walk, next_walk);
            if (state_to_path_pos.find(state) != state_to_path_pos.end()) { // cached
                // std::cout << "hit cache!" << std::endl;

                auto path_pos = state_to_path_pos[state];
                auto cycle_start_pos = state_to_cycle_start_pos[state];
                auto path_with_cycle = state_to_path_with_cycle[state];
                auto c_size = state_to_path_with_cycle[state]->size() - cycle_start_pos;

                // std::cout << "path pos " << path_pos << std::endl;
                // std::cout << "curr node " << (*path_with_cycle)[path_pos].first << std::endl;
                // std::cout << "cycle start pos " << cycle_start_pos << std::endl;
                // std::cout << "cyle start node " << (*path_with_cycle)[cycle_start_pos].first << std::endl;
                // std::cout << "g " << g << std::endl;

                // std::cout << "got path: " << std::endl;
                for (auto state_it = path_with_cycle->begin(); state_it != path_with_cycle->end(); ++state_it) {
                    // std::cout << (*state_it).first << " " << (*state_it).second << std::endl;
                }
                
                int g_rem;
                if (path_pos >= cycle_start_pos) { // already in cycle
                    // std::cout << "already in cycle!" << std::endl;
                    g_rem = g + (path_pos - cycle_start_pos);
                } else if (path_pos + g >= cycle_start_pos) { // can reach cycle
                    // std::cout << "can reach cycle" << std::endl;
                    g_rem = g - (cycle_start_pos - path_pos);
                } else { // cannot reach cycle, pos + g < is in path
                    // std::cout << "cannot reach cycle" << std::endl;
                    return (*path_with_cycle)[path_pos + g].first == P; // no need for modulo
                }

                // std::cout << "c_size " << c_size << std::endl;
                int idx = (cycle_start_pos) + (g_rem % c_size);
                int res = (*path_with_cycle)[idx].first;
                // std::cout << "using idx " << idx << std::endl;
                // std::cout << "getting res " << res << std::endl;

                return res == P;
            }

            if (visited.find(state) == visited.end()) {
                visited.insert(state);
                path->push_back(state);

                int temp = walk;
                walk = do_walk(walk, prev_walk);
                if (temp == walk) {
                    return walk == P; // we are stuck at walk
                }

                prev_walk = temp;
                next_walk = do_walk(walk, prev_walk);
            } else {
                // std::cout << "hit cycle!" << std::endl;
                // std::cout << "g remaining " << g << std::endl;
                // std::cout << "path: " << std::endl;
                for (int i = 0; i < path->size(); i++) {
                    // std::cout << (*path)[i].first << " " << (*path)[i].second << std::endl;
                }

                // std::cout << "state: " << state.first << " " << state.second << std::endl;

                auto cycle_start_it = std::find(path->begin(), path->end(), state);
                auto cycle_start_pos = std::distance(path->begin(), cycle_start_it);

                for (auto state_it = path->begin(); state_it != path->end(); ++state_it) {
                    // cache

                    auto path_pos = std::distance(path->begin(), state_it);
                    
                    state_to_path_pos.insert({*state_it, path_pos});
                    state_to_cycle_start_pos.insert({*state_it, cycle_start_pos});
                    state_to_path_with_cycle.insert({*state_it, path});
                }
                
                int c = std::distance(cycle_start_it, path->end());
                // std::cout << "cycle length " << c << std::endl;
                return (*path)[(cycle_start_pos) + (g % c)].first == P;
            }
        }

        // std::cout << "found path:" << '\n';
        for (int i = 0; i < path->size(); i ++) {
            // std::cout << (*path)[i].first << '\n';
        }
        // std::cout << "--------" << '\n';

        // After g steps, are we at P?
        return path->back().first == P;
    };

    for (int i = 0; i < Q; i++) {
        int g_val = G[i];
        int count = 0;
        // std::cout << "i " << i << std::endl;
        for (int node = 0; node < N; ++node) {
            // std::cout << "can from node: " << node << " " << g_val << std::endl;
            bool can = can_from_node(node, g_val);
            // std::cout << "can from node " << node << " " << g_val << ": " << can << std::endl;
            if (can) {
                count++;
            }
            // std::cout << "--------------------" << std::endl;
        }
        answer(count);


        // std::cout << "----------------------------------------" << std::endl;
    }
}

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