#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
struct TQuery {int x, y, tme;};
const int N = 1e5+2;
const int LN = 17;
const int INF = 1e9;
int n, q, ncyc, nextv[N], exp[N], tme, num[N], low[N], p[LN][N], f[LN][N], cycid[N], cycpos[N], h[N], din[N];
vector<int> g[N], scc[N];
stack<int> st;
TQuery r[N];
int offset[N];
class TTree
{
int it[1 << 18];
public:
void Update(int id, int sl, int sr, int u, int v)
{
if (sl == sr)
{
it[id] = v;
return;
}
int mid = (sl + sr) / 2;
if (u <= mid) Update(id*2+1, sl, mid, u, v);
else Update(id*2+2, mid+1, sr, u, v);
it[id] = min(it[id*2+1], it[id*2+2]);
}
int Query(int id, int sl, int sr, int ql, int qr)
{
if (sl > qr || sr < ql || ql > qr) return INF;
if (ql <= sl && sr <= qr) return it[id];
int mid = (sl + sr) / 2;
return min(Query(id*2+1, sl, mid, ql, qr), Query(id*2+2, mid+1, sr, ql, qr));
}
} tree;
void Dfs1(int u)
{
num[u] = low[u] = ++tme;
st.push(u);
if (nextv[u])
{
int v = nextv[u];
if (!num[v]) Dfs1(v), low[u] = min(low[u], low[v]);
else low[u] = min(low[u], num[v]);
}
if (low[u] == num[u])
{
++ncyc;
int x;
do
{
x = st.top(); st.pop();
scc[ncyc].push_back(x);
low[x] = num[x] = INF;
} while (x != u);
for (size_t i = 0; i < scc[ncyc].size(); ++i)
{
int v = scc[ncyc][i];
cycid[v] = ncyc;
cycpos[v] = i;
}
offset[ncyc] = offset[ncyc - 1];
if (scc[ncyc].size() > 1U)
{
int m = scc[ncyc].size();
offset[ncyc] += m;
for (int i = 0; i < m; ++i)
{
int v = scc[ncyc][i];
tree.Update(0, 0, n-1, offset[ncyc - 1] + i, exp[v]);
}
}
else f[0][ncyc] = exp[u];
}
}
void Dfs2(int u)
{
num[u] = 1;
for (int v: g[u])
{
h[v] = h[u] + 1;
p[0][v] = u;
Dfs2(v);
}
}
void BuildLCA()
{
for (int j = 1; j < LN; ++j)
for (int i = 1; i <= ncyc; ++i)
{
p[j][i] = p[j-1][p[j-1][i]];
f[j][i] = min(f[j-1][i], f[j-1][p[j-1][i]]);
}
}
int KthParent(int u, int k, int tme)
{
int low = INF;
for (int i = LN-1; i >= 0; --i)
if (k - (1 << i) >= 0)
{
low = min(low, f[i][u]);
u = p[i][u];
k -= 1 << i;
}
if (low < tme) return -1;
return u;
}
int QueryCycle(int cyc, int x, int y, int tme) // x -> y
{
int m = scc[cyc].size();
if (x < y)
{
return min(tree.Query(0, 0, n-1, offset[cyc - 1] + 0, offset[cyc - 1] + x),
tree.Query(0, 0, n-1, offset[cyc - 1] + y+1, offset[cyc - 1] + m-1))
> tme ? m - (y - x) : -1;
}
else return tree.Query(0, 0, n-1, offset[cyc - 1] + y+1, offset[cyc - 1] + x) > tme ? x - y : -1;
}
int Query(int x, int y, int tme) // x -> y
{
if (x == y) return 0;
if (cycid[x] == cycid[y])
{
int cyc = cycid[x];
x = cycpos[x], y = cycpos[y];
return QueryCycle(cyc, x, y, tme);
}
else // x and y do not belong to the same cycle
{
int u = cycid[x], v = cycid[y];
if (h[v] > h[u]) return -1;
int re = h[u] - h[v];
if (KthParent(u, h[u] - h[v], tme) != v) return -1;
if (scc[v].size() > 1) // v is a cycle
{
int val = QueryCycle(v, cycpos[nextv[scc[KthParent(u, h[u] - h[v] - 1, tme)][0]]], cycpos[y], tme);
return val == -1 ? -1 : re + val;
}
else return re;
}
}
void Solve()
{
for (int i = 1; i <= n; ++i)
if (!num[i]) Dfs1(i);
for (int i = 1; i <= n; ++i)
if (nextv[i] && cycid[nextv[i]] != cycid[i])
{
g[cycid[nextv[i]]].push_back(cycid[i]);
++din[cycid[i]];
}
fill(num+1, num+1+ncyc, 0);
for (int i = 1; i <= ncyc; ++i)
if (!din[i] && !num[i]) Dfs2(i); // start of chains
for (int i = 1; i <= ncyc; ++i)
if (!num[i]) Dfs2(i); // only cycles left
BuildLCA();
for (int i = 0; i < q; ++i)
{
int x = r[i].x, y = r[i].y, tme = r[i].tme;
printf("%d\n",Query(x, y, tme));
}
}
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
int queries;
scanf("%d",&queries);
fill(exp+1, exp+1+n, INF);
for (int i = 1, type, x, y; i <= queries; ++i)
{
scanf("%d",&type);
if (type == 1)
{
scanf("%d",&x); exp[x] = i;
}
else
{
scanf("%d%d",&x,&y);
r[q++] = {x, y, i};
}
}
Solve();
return 0;
}
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
specialg.cpp:184:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i = 1; i <= n; ++i) scanf("%d",&nextv[i]);
~~~~~^~~~~~~~~~~~~~~~
specialg.cpp:186:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&queries);
~~~~~^~~~~~~~~~~~~~~
specialg.cpp:190:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&type);
~~~~~^~~~~~~~~~~~
specialg.cpp:193:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x); exp[x] = i;
~~~~~^~~~~~~~~
specialg.cpp:197:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
5624 KB |
Output is correct |
| 2 |
Correct |
8 ms |
5864 KB |
Output is correct |
| 3 |
Correct |
8 ms |
5940 KB |
Output is correct |
| 4 |
Correct |
10 ms |
5940 KB |
Output is correct |
| 5 |
Correct |
8 ms |
5940 KB |
Output is correct |
| 6 |
Correct |
31 ms |
5940 KB |
Output is correct |
| 7 |
Correct |
18 ms |
6016 KB |
Output is correct |
| 8 |
Correct |
20 ms |
6040 KB |
Output is correct |
| 9 |
Correct |
30 ms |
6060 KB |
Output is correct |
| 10 |
Correct |
33 ms |
6188 KB |
Output is correct |
| 11 |
Correct |
130 ms |
19048 KB |
Output is correct |
| 12 |
Correct |
124 ms |
19048 KB |
Output is correct |
| 13 |
Correct |
133 ms |
20404 KB |
Output is correct |
| 14 |
Correct |
118 ms |
20404 KB |
Output is correct |
| 15 |
Correct |
131 ms |
20404 KB |
Output is correct |
| 16 |
Correct |
128 ms |
20404 KB |
Output is correct |
| 17 |
Correct |
154 ms |
23916 KB |
Output is correct |
| 18 |
Correct |
154 ms |
23952 KB |
Output is correct |
| 19 |
Correct |
172 ms |
24088 KB |
Output is correct |
| 20 |
Correct |
140 ms |
24088 KB |
Output is correct |
