#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
--a[i];
if (a[i] == -1) {
a[i] = i;
}
}
int q;
cin >> q;
vector<int> op(q), x(q), y(q);
for (int i = 0; i < q; i++) {
cin >> op[i];
if (op[i] == 1) {
cin >> x[i];
--x[i];
} else {
cin >> x[i] >> y[i];
--x[i]; --y[i];
}
}
vector<int> b(n, q);
for (int i = 0; i < q; i++) {
if (op[i] == 1) {
b[x[i]] = i;
}
}
vector<int> deg(n);
for (int i = 0; i < n; i++) {
deg[a[i]] += 1;
}
vector<int> que;
for (int i = 0; i < n; i++) {
if (deg[i] == 0) {
que.push_back(i);
}
}
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
deg[a[i]] -= 1;
if (deg[a[i]] == 0) {
que.push_back(a[i]);
}
}
vector<bool> on_cyc(n, true);
for (int i : que) {
on_cyc[i] = false;
}
vector<int> dep(n);
for (int b = (int) que.size() - 1; b >= 0; b--) {
int i = que[b];
dep[i] = dep[a[i]] + 1;
}
vector<int> pos(n);
vector<int> idx(n, -1);
vector<int> sz(n);
int T = 0;
for (int i = 0; i < n; i++) {
if (!on_cyc[i] || idx[i] != -1) {
continue;
}
int x = i;
int ptr = 0;
while (idx[x] == -1) {
pos[x] = ptr;
idx[x] = T;
sz[T] += 1;
ptr += 1;
x = a[x];
}
T += 1;
}
const int L = 20;
vector<vector<int>> jump(n, vector<int>(L));
for (int i = 0; i < n; i++) {
jump[i][0] = a[i];
}
for (int j = 1; j < L; j++) {
for (int i = 0; i < n; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
vector<vector<int>> mn(n, vector<int>(L));
for (int i = 0; i < n; i++) {
mn[i][0] = b[i];
}
for (int j = 1; j < L; j++) {
for (int i = 0; i < n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[jump[i][j - 1]][j - 1]);
}
}
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> root = [&](int x) {
return p[x] == x ? x : p[x] = root(p[x]);
};
for (int i = 0; i < n; i++) {
p[root(a[i])] = root(i);
}
for (int i = 0; i < q; i++) {
if (op[i] == 1) {
continue;
}
if (root(x[i]) != root(y[i]) || dep[x[i]] < dep[y[i]]) {
cout << -1 << '\n';
continue;
}
if (dep[y[i]] > 0) {
int v = x[i];
int d = dep[x[i]] - dep[y[i]];
for (int i = L - 1; i >= 0; i--) {
if (d >> i & 1) {
v = jump[v][i];
}
}
if (v != y[i]) {
cout << -1 << '\n';
continue;
}
int res = (int) 1e9;
for (int i = L - 1; i >= 0; i--) {
if (d >> i & 1) {
res = min(res, mn[v][i]);
v = jump[v][i];
}
}
if (res >= i) {
cout << d << '\n';
} else {
cout << -1 << '\n';
}
continue;
}
if (dep[x[i]] == 0) {
int d = (pos[y[i]] - pos[x[i]] + sz[idx[x[i]]]) % sz[idx[x[i]]];
int v = x[i];
int res = (int) 1e9;
for (int i = L - 1; i >= 0; i--) {
if (d >> i & 1) {
res = min(res, mn[v][i]);
v = jump[v][i];
}
}
if (res >= i) {
cout << d << '\n';
} else {
cout << -1 << '\n';
}
continue;
}
int v = x[i];
int d = 0;
int res = (int) 1e9;
{
for (int i = L - 1; i >= 0; i--) {
if (!on_cyc[jump[v][i]]) {
res = min(res, mn[v][i]);
d += (1 << i);
v = jump[v][i];
}
}
res = min(res, mn[v][0]);
v = a[v];
d += 1;
}
{
int w = (pos[y[i]] - pos[v] + sz[idx[v]]) % sz[idx[v]];
for (int i = L - 1; i >= 0; i--) {
if (w >> i & 1) {
res = min(res, mn[v][i]);
d += (1 << i);
v = jump[v][i];
}
}
}
if (res >= i) {
cout << d << '\n';
} else {
cout << -1 << '\n';
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
