#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());
}
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];
result += bucket.end()
- lower_bound(bucket.begin(), bucket.end(),
length);
}
if (second_cycle > 2 * nodes) {
if (length < 2 * nodes)
result += second_distances[length];
} else {
auto &bucket = second_buckets[length % second_cycle];
result += bucket.end()
- lower_bound(bucket.begin(), bucket.end(),
length);
}
answer(result);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
