#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
using llong = long long;
const int maxN = 100'000;
const int inf = 1000'000'000;
int unraw[maxN][2];
vector<int> nxt;
vector<int> nei[2 * maxN];
int depth[2 * maxN], tin[2 * maxN], tout[2 * maxN], par[2 * maxN];
void DFS(int v, int par)
{
static int tm = 0;
tin[v] = tm++;
depth[v] = (par == -1 ? 0 : depth[par] + 1);
for (int to: nei[v])
if (to != par)
DFS(to, v);
tout[v] = tm;
}
inline bool Upper(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
int root[2 * maxN], sz[2 * maxN];
void Init()
{
int n = nxt.size();
for (int i = 0; i < 2 * n; ++i)
{
par[i] = -1;
root[i] = i;
sz[i] = 1;
}
for (int i = 0; i < n; ++i)
{
unraw[i][0] = i;
unraw[i][1] = -1;
}
int stn = n;
vector<int> used(stn), col(stn, -1);
for (int i = 0; i < stn; ++i)
{
if (used[i]) continue;
int j = i;
int cyc = -1;
while (true)
{
if (used[j] == 0)
{
++used[j];
col[j] = i;
int to = nxt[j];
if (to == -1)
{
par[j] = -1;
break;
}
if (col[to] != i)
{
par[j] = to;
nei[to].push_back(j);
j = to;
}
else
{
cyc = j;
break;
}
}
else
break;
}
if (cyc != -1)
{
int rawj = cyc, j = cyc;
while (true)
{
int rawto = nxt[rawj];
if (used[rawto] == 2)
break;
++used[rawto];
int to = n++;
unraw[rawto][1] = to;
par[j] = to;
nei[to].push_back(j);
rawj = rawto;
j = to;
}
}
}
vector<bool> isRoot(n, false);
for (int i = 0; i < n; ++i)
if (par[i] == -1)
isRoot[i] = true;
for (int i = 0; i < n; ++i)
if (isRoot[i])
DFS(i, -1);
}
int Root(int v)
{
return (root[v] == v ? v : root[v] = Root(root[v]));
}
void Union(int u, int v)
{
#ifdef MANSON
cerr << "Union(" << u << ", " << v << ")\n";
#endif
u = Root(u); v = Root(v);
if (u == v) return;
if (sz[u] > sz[v]) swap(u, v);
root[u] = v;
sz[v] += sz[u];
}
void Add(int v)
{
#ifdef MANSON
cerr << "v: " << v << ", par: " << par[v] << '\n';
#endif
if (par[v] == -1) return;
Union(v, par[v]);
}
int Dist(int u, int v)
{
swap(u, v);
if (u == 4 && v == 2)
cerr << "";
if (!Upper(u, v) || Root(u) != Root(v))
return inf;
return depth[v] - depth[u];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
nxt.resize(n);
vector<bool> isdel(n, true);
for (int i = 0; i < n; ++i)
{
cin >> nxt[i];
if (nxt[i])
isdel[i] = false;
--nxt[i];
}
Init();
int qnum;
cin >> qnum;
vector<vector<int>> qs(qnum);
for (vector<int>& q: qs)
{
int type;
cin >> type;
if (type == 1)
{
q.resize(1);
cin >> q[0]; --q[0];
isdel[q[0]] = true;
}
else
{
q.resize(2);
cin >> q[0] >> q[1]; --q[0]; --q[1];
}
}
for (int i = 0; i < n; ++i)
if (!isdel[i])
qs.push_back({i});
reverse(qs.begin(), qs.end());
for (vector<int>& q: qs)
{
int type = q.size();
if (type == 1)
{
int raw = q[0];
for (int i = 0; i < 2; ++i)
if (unraw[raw][i] != -1)
Add(unraw[raw][i]);
}
else
{
int rawu = q[0], rawv = q[1];
vector<int> us = {unraw[rawu][0], unraw[rawu][1]};
vector<int> vs = {unraw[rawv][0], unraw[rawv][1]};
int ans = inf;
for (int u: us)
if (u != -1)
for (int v: vs)
if (v != -1)
ans = min(ans, Dist(u, v));
if (ans == inf)
q.push_back(-1);
else
q.push_back(ans);
}
}
reverse(qs.begin(), qs.end());
for (auto& q: qs)
if (q.size() == 3)
cout << q.back() << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
5504 KB |
Output is correct |
| 2 |
Correct |
9 ms |
5504 KB |
Output is correct |
| 3 |
Correct |
10 ms |
5504 KB |
Output is correct |
| 4 |
Correct |
13 ms |
6016 KB |
Output is correct |
| 5 |
Correct |
9 ms |
5632 KB |
Output is correct |
| 6 |
Correct |
20 ms |
7040 KB |
Output is correct |
| 7 |
Correct |
18 ms |
7040 KB |
Output is correct |
| 8 |
Correct |
20 ms |
7040 KB |
Output is correct |
| 9 |
Correct |
18 ms |
7040 KB |
Output is correct |
| 10 |
Correct |
20 ms |
7168 KB |
Output is correct |
| 11 |
Correct |
118 ms |
39868 KB |
Output is correct |
| 12 |
Correct |
92 ms |
24712 KB |
Output is correct |
| 13 |
Correct |
103 ms |
29032 KB |
Output is correct |
| 14 |
Correct |
94 ms |
23104 KB |
Output is correct |
| 15 |
Correct |
99 ms |
25328 KB |
Output is correct |
| 16 |
Correct |
96 ms |
25088 KB |
Output is correct |
| 17 |
Correct |
112 ms |
33640 KB |
Output is correct |
| 18 |
Correct |
111 ms |
33592 KB |
Output is correct |
| 19 |
Correct |
110 ms |
33596 KB |
Output is correct |
| 20 |
Correct |
117 ms |
40008 KB |
Output is correct |
