CSES - Shared codeLink to this code:
https://cses.fi/paste/922006d81d0afa047a2e9c/
#include <algorithm>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifndef LOCAL
#endif
#define all(x) (x).begin(), (x).end()
typedef long long ll;
template <typename Key, typename Cmp = less<Key>>
using ordered_set =
tree<Key, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename Key, typename Value, typename Cmp = less<Key>>
using ordered_map =
tree<Key, Value, Cmp, rb_tree_tag, tree_order_statistics_node_update>;
template <typename Key>
using min_heap = priority_queue<Key, vector<Key>, greater<Key>>;
template <typename Tp> class vect1 : public vector<Tp> {
public:
using vector<Tp>::vector;
Tp& operator[](size_t idx) {
return this->at(idx - 1);
}
};
#define int long long
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vect1<int> next(n);
vect1<vect1<int>> before(n);
for (int i = 1; i <= n; i++)
cin >> next[i], before[next[i]].emplace_back(i);
vector<vect1<int>> binlift(31, vect1<int>(n));
{
binlift[0] = next;
for (int i = 1; i <= 30; i++)
for (int j = 1; j <= n; j++)
binlift[i][j] = binlift[i - 1][binlift[i - 1][j]];
}
vector<bool> processed(n + 1, false), in_cycle(n + 1, false);
vect1<int> destcycle(n);
vect1<vect1<int>> cycles;
for (int cur = 1; cur <= n; cur++) {
if (processed[cur])
continue;
int at = cur;
vect1<int> path;
set<int> onpath;
path.emplace_back(at);
onpath.insert(at);
while (!processed[next[at]]) {
at = next[at];
processed[at] = true;
path.emplace_back(at);
onpath.insert(at);
}
if (onpath.count(next[path.back()]) == 0) {
for (auto& pathel : path)
destcycle[pathel] = destcycle[next[path.back()]];
} else {
reverse(all(path));
deque<int> cycle;
int pidx = 1;
cycle.push_back(path[pidx++]);
while (next[cycle.front()] != cycle.back()) {
cycle.push_back(path[pidx++]);
}
for (auto& cycleel : cycle)
in_cycle[cycleel] = true;
reverse(all(cycle));
cycles.emplace_back(vect1<int>(all(cycle)));
for (auto& pathel : path)
destcycle[pathel] = cycles.size();
}
}
vect1<int> cycledist(n, INT_MAX);
{
vector<bool> visited(n + 1, 0);
queue<int> bfsq;
for (int i = 1; i <= n; i++)
if (in_cycle[i])
cycledist[i] = 0, bfsq.push(i), visited[i] = true;
while (!bfsq.empty()) {
auto cur = bfsq.front();
bfsq.pop();
for (auto& fr : before[cur]) {
if (!visited[fr]) {
visited[fr] = true;
cycledist[fr] = cycledist[cur] + 1;
bfsq.push(fr);
}
}
}
}
auto lift = [&](int cur, int dist) {
for (int i = 0; i <= 30; i++)
if (dist & (1 << i)) {
cur = binlift[i][cur];
}
return cur;
};
vect1<int> cyclepos(n);
for (auto& cycle : cycles) {
for (int i = 1; i <= cycle.size(); i++)
cyclepos[cycle[i]] = i;
}
while (q--) {
int a, b;
cin >> a >> b;
if (destcycle[a] != destcycle[b]) {
cout << "-1\n";
continue;
}
if (in_cycle[a] && in_cycle[b]) {
if (cyclepos[b] >= cyclepos[a]) {
cout << cyclepos[b] - cyclepos[a];
} else
cout << cycles[destcycle[b]].size() - (cyclepos[a] - cyclepos[b]);
cout << '\n';
continue;
}
if ((!in_cycle[a]) && (!in_cycle[b])) {
if (cycledist[a] < cycledist[b]) {
cout << "-1\n";
continue;
} else {
int d = cycledist[a] - cycledist[b];
a = lift(a, d);
if (a == b) {
cout << d << '\n';
continue;
} else {
cout << "-1\n";
continue;
}
}
}
if (in_cycle[a] && (!in_cycle[b])) {
cout << "-1\n";
continue;
}
if ((!in_cycle[a]) && in_cycle[b]) {
int d = cycledist[a];
a = lift(a, d);
if (cyclepos[b] >= cyclepos[a]) {
cout << d + cyclepos[b] - cyclepos[a];
} else
cout << d + cycles[destcycle[b]].size() - (cyclepos[a] - cyclepos[b]);
cout << '\n';
}
}
}