oj.uz

Submission #854522

# Submission time Handle Problem Language Result Execution time Memory
854522 2023-09-27T19:54:57 Z marximimus Tropical Garden (IOI11_garden) C++17
100 / 100
 102 ms 42064 KB 
#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.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 9 ms 6376 KB Output is correct
12 Correct 18 ms 9048 KB Output is correct
13 Correct 57 ms 31568 KB Output is correct
14 Correct 59 ms 24656 KB Output is correct
15 Correct 102 ms 25672 KB Output is correct
16 Correct 55 ms 19688 KB Output is correct
17 Correct 50 ms 18000 KB Output is correct
18 Correct 19 ms 9564 KB Output is correct
19 Correct 61 ms 24756 KB Output is correct
20 Correct 75 ms 25520 KB Output is correct
21 Correct 65 ms 20136 KB Output is correct
22 Correct 53 ms 17492 KB Output is correct
23 Correct 63 ms 26840 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 9 ms 6376 KB Output is correct
12 Correct 18 ms 9048 KB Output is correct
13 Correct 57 ms 31568 KB Output is correct
14 Correct 59 ms 24656 KB Output is correct
15 Correct 102 ms 25672 KB Output is correct
16 Correct 55 ms 19688 KB Output is correct
17 Correct 50 ms 18000 KB Output is correct
18 Correct 19 ms 9564 KB Output is correct
19 Correct 61 ms 24756 KB Output is correct
20 Correct 75 ms 25520 KB Output is correct
21 Correct 65 ms 20136 KB Output is correct
22 Correct 53 ms 17492 KB Output is correct
23 Correct 63 ms 26840 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 9 ms 6456 KB Output is correct
26 Correct 19 ms 9048 KB Output is correct
27 Correct 54 ms 31568 KB Output is correct
28 Correct 61 ms 24776 KB Output is correct
29 Correct 73 ms 25776 KB Output is correct
30 Correct 59 ms 19536 KB Output is correct
31 Correct 53 ms 18256 KB Output is correct
32 Correct 19 ms 9820 KB Output is correct
33 Correct 65 ms 24772 KB Output is correct
34 Correct 71 ms 25680 KB Output is correct
35 Correct 59 ms 20272 KB Output is correct
36 Correct 52 ms 18020 KB Output is correct
37 Correct 63 ms 26960 KB Output is correct
38 Correct 82 ms 42064 KB Output is correct