Submission #1218024

#TimeUsernameProblemLanguageResultExecution timeMemory
1218024asturnoxTropical Garden (IOI11_garden)C++20
49 / 100
5096 ms48444 KiB
#include <iostream> #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>, pair<int, int>> state_to_cycle_start; map<pair<int, int>, shared_ptr<deque<pair<int, int>> >> state_to_path; map<pair<int, int>, shared_ptr<deque<pair<int, int>> >> state_to_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.find(state) != state_to_path.end()) { // cached auto cached_path = state_to_path[state]; auto cycle_start = state_to_cycle_start[state]; // std::cout << "hit cache!" << std::endl; auto it = std::find(cached_path->begin(), cached_path->end(), state); auto it_cycle_start = std::find(cached_path->begin(), cached_path->end(), cycle_start); if (it != cached_path->end()) { size_t pos = std::distance(cached_path->begin(), it); size_t pos_cycle = std::distance(cached_path->begin(), it_cycle_start); int start_pos; int g_rem; if (pos >= pos_cycle) { // already in cycle // std::cout << "already in cycle!" << std::endl; start_pos = pos; g_rem = g; } else if (pos + g >= pos_cycle) { // can reach cycle start_pos = pos_cycle; g_rem = g - (pos_cycle - pos); } else { // cannot reach cycle, pos + g < is in path return (*cached_path)[pos + g].first == P; // no need for modulo } // get cycle auto cycle = state_to_cycle[cycle_start]; // now cycle auto c_size = cycle->size(); return (*cycle)[(start_pos + g_rem) % c_size].first == P; } else { // std::cout << "ERROR, not in cycle" << std::endl; throw std::runtime_error("State not found in cached cycle"); } } 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 = make_shared<deque<pair<int, int>>>(*path); while (cycle->front() != state) { // std::cout << "popping " << cycle.front().first << " " << cycle.front().second << std::endl; cycle->pop_front(); } // now have a cycle for (auto state_it = path->begin(); state_it != path->end(); ++state_it) { // cache state_to_path.insert({*state_it, path}); state_to_cycle_start.insert({*state_it, state}); state_to_cycle.insert({*state_it, cycle}); } int c = cycle->size(); // std::cout << "cycle length " << c << std::endl; return (*cycle)[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; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...