Submission #1217270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217270		asturnox	Tropical Garden (IOI11_garden)	C++20	Compilation error	0 ms	0 KiB

garden

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

    // Can we, starting from `node`, after g steps end up at node P?
    auto can_from_node = [&](int node, int g) {
        g++; // since we want to count how many trails we take

        deque<pair<int,int>> path;
        set<pair<int,int>> visited;

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

        while (g > 0) {
            pair<int,int> state = make_pair(walk, next_walk);
            if (visited.find(state) == visited.end()) {
                visited.insert(state);
                path.push_back(state);

                int temp = walk;
                walk = do_walk(walk, prev_walk);
                prev_walk = temp;
                next_walk = do_walk(walk, prev_walk);
                --g;
            } else {
                // We've hit a cycle; trim path to just the cycle
                // std::cout << "hit cycle!" << '\n';
                while (path.front() != state) {
                    path.pop_front();
                }
                int c = path.size();
                return path[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;
        for (int node = 1; node <= N; ++node) {
            if (can_from_node(node, g_val)) {
                count++;
            }
        }
        answer(count);
    }
}

Compilation message (stderr)

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:5:12: error: 'vector' was not declared in this scope
    5 |     vector<vector<int>> node_edges(N + 1);
      |            ^~~~~~
garden.cpp:5:19: error: expected primary-expression before 'int'
    5 |     vector<vector<int>> node_edges(N + 1);
      |                   ^~~
garden.cpp:9:13: error: 'node_edges' was not declared in this scope
    9 |         if (node_edges[i].size() < 2) {
      |             ^~~~~~~~~~
garden.cpp:12:13: error: 'node_edges' was not declared in this scope
   12 |         if (node_edges[j].size() < 2) {
      |             ^~~~~~~~~~
garden.cpp: In lambda function:
garden.cpp:19:13: error: 'node_edges' was not declared in this scope
   19 |         if (node_edges[walk].empty()) {
      |             ^~~~~~~~~~
garden.cpp:23:25: error: 'node_edges' was not declared in this scope
   23 |         int next_walk = node_edges[walk][0];
      |                         ^~~~~~~~~~
garden.cpp: In lambda function:
garden.cpp:34:15: error: 'pair' was not declared in this scope
   34 |         deque<pair<int,int>> path;
      |               ^~~~
garden.cpp:34:9: error: 'deque' was not declared in this scope
   34 |         deque<pair<int,int>> path;
      |         ^~~~~
garden.cpp:34:20: error: expected primary-expression before 'int'
   34 |         deque<pair<int,int>> path;
      |                    ^~~
garden.cpp:35:9: error: 'set' was not declared in this scope
   35 |         set<pair<int,int>> visited;
      |         ^~~
garden.cpp:35:18: error: expected primary-expression before 'int'
   35 |         set<pair<int,int>> visited;
      |                  ^~~
garden.cpp:42:18: error: expected primary-expression before 'int'
   42 |             pair<int,int> state = make_pair(walk, next_walk);
      |                  ^~~
garden.cpp:43:17: error: 'visited' was not declared in this scope
   43 |             if (visited.find(state) == visited.end()) {
      |                 ^~~~~~~
garden.cpp:43:30: error: 'state' was not declared in this scope; did you mean 'static'?
   43 |             if (visited.find(state) == visited.end()) {
      |                              ^~~~~
      |                              static
garden.cpp:45:17: error: 'path' was not declared in this scope
   45 |                 path.push_back(state);
      |                 ^~~~
garden.cpp:55:24: error: 'path' was not declared in this scope
   55 |                 while (path.front() != state) {
      |                        ^~~~
garden.cpp:58:25: error: 'path' was not declared in this scope
   58 |                 int c = path.size();
      |                         ^~~~
garden.cpp:64:29: error: 'path' was not declared in this scope
   64 |         for (int i = 0; i < path.size(); i ++) {
      |                             ^~~~
garden.cpp:70:16: error: 'path' was not declared in this scope
   70 |         return path.back().first == P;
      |                ^~~~