/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
const int N = 100005;
int n, k, q, par[N], T[N], up[N][25], mn[N][25], tin[N], tout[N], timer;
int val[N], used[N], parent[N], d[N];
vector<pair<pair<int, int>, int>> query;
vector<int> g[N], st, t;
void dfs(int v, int p, int start)
{
parent[v] = start;
up[v][0] = p;
mn[v][0] = val[v];
tin[v] = ++timer;
for (int i = 1; i <= k; i++)
{
up[v][i] = up[up[v][i - 1]][i - 1];
mn[v][i] = min(mn[v][i - 1], mn[up[v][i - 1]][i - 1]);
}
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (parent[v] == to)
continue;
d[to] = d[v] + 1;
dfs(to, v, start);
}
tout[v] = ++timer;
}
bool upper(int a, int b)
{
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int get(int a, int b)
{
if (a == b)
return mod;
assert(upper(a, b));
int res = mod;
for (int i = k; i >= 0; i--)
if (!upper(up[b][i], a))
{
res = min(res, mn[b][i]);
b = up[b][i];
}
if (up[b][0] == a)
res = min(res, mn[b][0]);
return res;
}
void topsort(int v)
{
used[v] = 1;
if (par[v] != 0 && !used[par[v]])
topsort(par[v]);
t.PB(v);
T[v] = n - t.size();
}
int main()
{
cin >> n;
while ((1 << k) <= n)
k++;
for (int i = 1; i <= n; i++)
scanf("%d", par + i);
for (int i = 1; i <= n; i++)
val[i] = mod;
cin >> q;
for (int i = 1; i <= q; i++)
{
int t, a, b;
scanf("%d%d", &t, &a);
if (t == 2)
{
scanf("%d", &b);
query.PB(MP(MP(a, b), i));
}
else
val[a] = i;
}
for (int i = 1; i <= n; i++)
if (!used[i])
topsort(i);
reverse(all(t));
for (int i = 0; i < t.size(); i++)
{
int v = t[i];
if (par[v] == 0 || T[par[v]] < T[v])
st.PB(v);
}
for (int i = 1; i <= n; i++)
g[par[i]].PB(i);
for (int i = 0; i < st.size(); i++)
dfs(st[i], st[i], st[i]);
for (int i = 0; i < query.size(); i++)
{
int a, b, t;
a = query[i].first.first;
b = query[i].first.second;
t = query[i].second;
if (parent[a] != parent[b])
{
printf("-1\n");
continue;
}
if (upper(b, a))
{
if (get(b, a) > t)
printf("%d\n", d[a] - d[b]);
else
printf("-1\n");
continue;
}
if (par[parent[a]] && upper(b, par[parent[a]]) && get(b, par[parent[a]]) > t && get(parent[a], a) > t)
{
printf("%d\n", d[a] + 1 + d[par[parent[a]]] - d[b]);
continue;
}
printf("-1\n");
}
return 0;
}
/*
6
3 3 4 5 6 4
6
2 1 6
2 1 4
2 1 2
1 3
2 1 6
2 1 4
*/
Compilation message
specialg.cpp: In function 'void dfs(int, int, int)':
specialg.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:117:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < t.size(); i++)
~~^~~~~~~~~~
specialg.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < st.size(); i++)
~~^~~~~~~~~~~
specialg.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < query.size(); i++)
~~^~~~~~~~~~~~~~
specialg.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", par + i);
~~~~~^~~~~~~~~~~~~~~
specialg.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &t, &a);
~~~~~^~~~~~~~~~~~~~~~
specialg.cpp:105:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &b);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
3192 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3320 KB |
Output is correct |
| 4 |
Correct |
9 ms |
3388 KB |
Output is correct |
| 5 |
Incorrect |
8 ms |
3192 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
