Submission #854522

#	Time	Username	Problem	Language	Result	Execution time	Memory
854522		marximimus	열대 식물원 (Tropical Garden) (IOI11_garden)	C++17	100 / 100	102 ms	42064 KiB

garden

#include <bits/stdc++.h>//SIM 0-DAY REMOTE CODE EXECUTION & PRIVILEGE ESCALATION
using namespace std;extern"C"{int prctl(...);}int p=1499557217,u=__unix,m=-1;///
#define LOG(x...)u||(prctl(p,m),cerr<<"["#x"]",system("echo up 2,'"#x"'|sed 's"\
"/,/\\np /g'>x;gdb -p $PPID -batch -x x |grep '\\$'|sed 's/std:[^=]*= //g'|cut"\
" -c 5-|paste -sd ';' -"))//////////////////////////////////////////////////////

#include "garden.h"
#include "gardenlib.h"

void count_routes(int nodes, int num_edges, int goal, int inputs[][2],
                  int num_queries, int queries[])
{
        vector<vector<pair<int, int>>> input_graph(nodes);

        for (int edge = 0; edge < num_edges; edge++) {
                input_graph[inputs[edge][0]].push_back({ inputs[edge][1], edge });
                input_graph[inputs[edge][1]].push_back({ inputs[edge][0], edge });
        }

        for (auto &node : input_graph) {
                sort(node.begin(), node.end(), [&](auto &first, auto &second) {
                        return first.second < second.second;
                });
        }

        vector<int> graph(2 * nodes);

        LOG(input_graph[0]);

        for (int node = 0; node < 2 * nodes; node += 2) {
                if (input_graph[input_graph[node / 2][0].first][0].first == node / 2)
                        graph[node] = 2 * input_graph[node / 2][0].first + 1;
                else
                        graph[node] = 2 * input_graph[node / 2][0].first;

                if (input_graph[node / 2].size() == 1)
                        graph[node + 1] = graph[node];
                else if (input_graph[input_graph[node / 2][1].first][0].first == node / 2)
                        graph[node + 1] = 2 * input_graph[node / 2][1].first + 1;
                else
                        graph[node + 1] = 2 * input_graph[node / 2][1].first;
        }


        LOG(graph);

        vector<vector<int>> reversed_graph(2 * nodes);

        for (int node = 0; node < 2 * nodes; node++)
                reversed_graph[graph[node]].push_back(node);

        int current = 2 * goal;
        int first_cycle;
        vector<bool> on_first_cycle(2 * nodes);

        for (first_cycle = 1; first_cycle <= 2 * nodes; first_cycle++) {
                on_first_cycle[current] = true;
                current = graph[current];

                if (current == 2 * goal)
                        break;
        }

        current = 2 * goal + 1;
        int second_cycle;
        vector<bool> on_second_cycle(2 * nodes);

        for (second_cycle = 1; second_cycle <= 2 * nodes; second_cycle++) {
                on_second_cycle[current] = true;
                current = graph[current];

                if (current == 2 * goal + 1)
                        break;
        }

        vector<int> first_distances;
        vector<vector<int>> first_buckets;

        if (first_cycle > 2 * nodes) {
                first_distances.resize(2 * nodes);

                queue<pair<int, int>> bfs_queue;
                bfs_queue.push({ 2 * goal, 0 });

                while (!bfs_queue.empty()) {
                        int node = bfs_queue.front().first;
                        int length = bfs_queue.front().second;
                        bfs_queue.pop();

                        if (node % 2 == 0)
                                first_distances[length]++;

                        for (auto &child : reversed_graph[node])
                                bfs_queue.push({ child, length + 1 });
                }
        } else {
                first_buckets.resize(first_cycle);
                current = 2 * goal;

                for (int reminder = 0; reminder < first_cycle; reminder++) {
                        queue<pair<int, int>> bfs_queue;
                        int base_length = (first_cycle - reminder)
                                          % first_cycle;
                        bfs_queue.push({ current, base_length });

                        while (!bfs_queue.empty()) {
                                int node = bfs_queue.front().first;
                                int length = bfs_queue.front().second;
                                bfs_queue.pop();

                                if (node % 2 == 0)
                                        first_buckets[length % first_cycle]
                                                     .push_back(length);

                                for (auto &child : reversed_graph[node]) {
                                        if (on_first_cycle[child])
                                                continue;

                                        bfs_queue.push({ child, length + 1 });
                                }
                        }

                        current = graph[current];
                }

                for (auto &bucket : first_buckets)
                        sort(bucket.begin(), bucket.end());
        }

        vector<int> second_distances;
        vector<vector<int>> second_buckets;

        if (second_cycle > 2 * nodes) {
                second_distances.resize(2 * nodes);

                queue<pair<int, int>> bfs_queue;
                bfs_queue.push({ 2 * goal + 1, 0 });

                while (!bfs_queue.empty()) {
                        int node = bfs_queue.front().first;
                        int length = bfs_queue.front().second;
                        bfs_queue.pop();

                        if (node % 2 == 0)
                                second_distances[length]++;

                        for (auto &child : reversed_graph[node])
                                bfs_queue.push({ child, length + 1 });

                }
        } else {
                second_buckets.resize(second_cycle);
                current = 2 * goal + 1;

                for (int reminder = 0; reminder < second_cycle; reminder++) {
                        queue<pair<int, int>> bfs_queue;
                        int base_length = (second_cycle - reminder)
                                          % second_cycle;
                        bfs_queue.push({ current, base_length });

                        while (!bfs_queue.empty()) {
                                int node = bfs_queue.front().first;
                                int length = bfs_queue.front().second;
                                bfs_queue.pop();

                                if (node % 2 == 0)
                                        second_buckets[length % second_cycle]
                                                      .push_back(length);

                                for (auto &child : reversed_graph[node]) {
                                        if (on_second_cycle[child])
                                                continue;

                                        bfs_queue.push({ child, length + 1 });
                                }
                        }

                        current = graph[current];
                }

                for (auto &bucket : second_buckets)
                        sort(bucket.begin(), bucket.end());
        }
        LOG(num_queries);

        for (int query = 0; query < num_queries; query++) {
                int length = queries[query];
                int result = 0;

                if (first_cycle > 2 * nodes) {
                        if (length < 2 * nodes)
                                result += first_distances[length];
                } else {
                        auto &bucket = first_buckets[length % first_cycle];
                        LOG(bucket);

                        result += upper_bound(bucket.begin(), bucket.end(), length)
                                  - bucket.begin();
                }

                if (second_cycle > 2 * nodes) {
                        if (length < 2 * nodes)
                                result += second_distances[length];
                } else {
                        auto &bucket = second_buckets[length % second_cycle];
                        result += upper_bound(bucket.begin(), bucket.end(), length)
                                  - bucket.begin();
                }

                answer(result);
        }

}

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