#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 18;
int n, nxt[N], dp[M + 1][N], p[N], d[N], cnt[N], cl[N], num[N], lg[N];
int m, cur, sz, x[N], y[N], type[N], ans[N];
bool circle[N], used[N];
vector < int > g[N];
void dfs1(int v){
for(int to : g[v]){
if(to != dp[0][v]){
d[to] = d[v] + 1;
dfs1(to);
}
}
}
void dfs2(int v){
num[v] = ++lg[sz];
cl[v] = sz;
if(!cl[nxt[v]]){
dfs2(nxt[v]);
}
}
int dsu_get(int v){
return p[v] == v ? v : p[v] = dsu_get(p[v]);
}
/// X podveshivaem k Y
inline void dsu_unite(int x, int y){
x = dsu_get(x);
y = dsu_get(y);
if(x == y){
circle[x] = true;
return;
}
p[x] = y;
}
inline int lca(int x, int y){
for(int i = M; i >= 0; i--){
if(d[dp[i][x]] >= d[y]){
x = dp[i][x];
}
}
return x;
}
int main(){
freopen("specialg.in", "r", stdin);
freopen("specialg.out", "w", stdout);
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> nxt[i];
if(nxt[i]){
cnt[nxt[i]]++;
}
p[i] = i;
}
queue < int > q;
for(int i = 1; i <= n; i++){
if(!cnt[i]){
q.push(i);
}
}
while(!q.empty()){
int v = q.front();
q.pop();
if(nxt[v]){
cnt[nxt[v]]--;
if(!cnt[nxt[v]]){
q.push(nxt[v]);
}
}
}
for(int i = 1; i <= n; i++){
if(nxt[i] && !cnt[i]){
g[nxt[i]].push_back(i);
dp[0][i] = nxt[i];
}
}
for(int i = 1; i <= n; i++){
if(!dp[0][i]){
dp[0][i] = i;
dfs1(i);
}
}
for(int j = 1; j <= M; j++){
for(int i = 1; i <= n; i++){
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
for(int i = 1; i <= n; i++){
if(!cl[i] && cnt[i]){
sz++;
dfs2(i);
}
}
/*for(int i = 1; i <= n; i++){
for(int j = 0; j <= M; j++){
cout << dp[j][i] << " ";
}
cout << "\n";
}
return 0;*/
cin >> m;
for(int i = 1; i <= m; i++){
cin >> type[i] >> x[i];
if(type[i] == 1){
used[x[i]] = true;
}
else{
cin >> y[i];
}
}
//return 0;
for(int i = 1; i <= n; i++){
if(!used[i] && nxt[i]){
dsu_unite(i, nxt[i]);
}
}
/*for(int i = 1; i <= n; i++){
cout << dsu_get(i) << " ";
}
return 0;*/
//cout << "\n";
for(int i = m; i >= 1; i--){
if(type[i] == 1){
dsu_unite(x[i], nxt[x[i]]);
}
else{
int px = dsu_get(x[i]),
py = dsu_get(y[i]);
if(px == py){
if(lca(x[i], y[i]) == y[i]){
ans[i] = d[x[i]] - d[y[i]];
}
else{
//cout << "SOSI " << lca(x[i], y[i]) << " " << px << " " << py << " " << x[i] << " " << y[i] << "\n";
int z = dp[M][x[i]];
if(!cl[px] || !cl[z] || cl[z] != cl[y[i]]){
ans[i] = -1;
}
else{
ans[i] = d[x[i]] + (num[y[i]] - num[z]);
//cout << "CIRCLE = " << circle[px] << " " << num[y[i]] << " " << z << " " << num[z] << "\n";
if(!circle[px]){
if(num[z] < num[y[i]]){
if(num[px] < num[y[i]] && num[z] <= num[y[i]]){
ans[i] = -1;
}
}
else{
if(num[px] < num[y[i]] || num[z] <= num[y[i]]){
ans[i] = -1;
}
else{
ans[i] += lg[cl[y[i]]];
}
}
}
else{
if(num[z] > num[y[i]]){
ans[i] += lg[cl[y[i]]];
}
}
}
}
}
else{
ans[i] = -1;
}
}
}
for(int i = 1; i <= m; i++){
if(type[i] == 2){
cout << ans[i] << "\n";
}
}
}
/**
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
2 1 3
*/
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("specialg.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
specialg.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("specialg.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
