#include<bits/stdc++.h>
using namespace std;
const int N = 1 << 17;
const int INF = 1e+9;
int n, a[100001];
int m, t, u, v, incycle, kk;
int td[100001];
vector<int> g[100001];
vector< pair<int, int> > q[100001];
vector< pair<int, int> > ans;
int us[100001];
int st1[2 * N], st2[2 * N], pos[100001];
int fcycle(int x) {
if (us[x] == 1) return x;
if (a[x] == 0) return x;
us[x] = 1;
return fcycle(a[x]);
}
int getmin(int T, int ll, int rr, int L, int R) {
//cout << "getmin(" << T << ", " << ll << ", " << rr << ", " << L << ", " << R << ")" << endl;
if (L > R) return INF;
if (ll == L && rr == R) return st2[T];
int mm = (ll + rr) / 2;
return min(getmin(T*2, ll, mm, L, min(R,mm)), getmin(T*2+1, mm+1, rr, max(L,mm+1), R));
}
int getmin2(int T, int ll, int rr, int L, int R) {
//cout << "getmin2(" << T << ", " << ll << ", " << rr << ", " << L << ", " << R << ")" << endl;
if (L > R) return INF;
if (ll == L && rr == R) return st1[T];
int mm = (ll + rr) / 2;
return min(getmin2(T*2, ll, mm, L, min(R,mm)), getmin2(T*2+1, mm+1, rr, max(L,mm+1), R));
}
void dfs(int x, int dep) {
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "looking for queries... " << q[x].size() << endl;
for (int j = 0; j < q[x].size(); j++) {
int r = q[x][j].first;
int w = q[x][j].second;
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << r << " is on ";
int h = -1;
if (us[r] == 1) {
//cout << "path\n";
int z = getmin(1, 0, N-1, pos[r], dep - 1);
if (z < w) h = -1;
else h = dep - 1 - pos[r];
}
if (us[r] == 2) {
//cout << "loop\n";
int z1 = getmin(1, 0, N-1, 0, dep - 1);
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "min on path = " << z1 << endl;
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "pos[" << incycle << "] = " << pos[incycle] << endl;
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "pos[" << r << "] = " << pos[r] << endl;
int z2;
if (pos[incycle] <= pos[r])
z2 = getmin2(1, 0, N-1, pos[incycle], pos[r] - 1);
else
z2 = min(getmin2(1, 0, N-1, pos[incycle], kk - 1),
getmin2(1, 0, N-1, 0, pos[r] - 1));
if (min(z1, z2) < w) h = -1;
else {
h = dep;
if (pos[incycle] <= pos[r])
h += pos[r] - pos[incycle];
else
h += pos[r] + (kk - pos[incycle]);
}
}
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "distance to " << r << " at moment " << w << " = " << h << endl;
ans.push_back({w, h});
}
for (int i = 0; i < g[x].size(); i++) {
int to = g[x][i];
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "to = " << to << endl;
if (us[to] == 0) {
//for (int i = 0; i < dep; i++) cout << "\t";
//cout << "went to " << to << endl;
pos[to] = dep;
us[to] = 1;
st2[N + dep] = td[to];
int p = (N + dep) / 2;
while (p > 0) {
st2[p] = min(st2[2 * p], st2[2 * p + 1]);
p = p / 2;
}
dfs(to, dep + 1);
pos[to] = 0;
us[to] = 3;
st2[N + dep] = INF;
p = (N + dep) / 2;
while (p > 0) {
st2[p] = min(st2[2 * p], st2[2 * p + 1]);
p = p / 2;
}
}
}
}
int main() {
//freopen("specialg.in", "r", stdin);
//freopen("specialg.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0) a[i] = a[i];
g[a[i]].push_back(i);
td[i] = INF;
}
//for (int i = 1; i <= n; i++) {
//cout << i << ": ";
//for (int j = 0; j < g[i].size(); j++)
//cout << g[i][j] << " ";
//cout << endl;
//}
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> t;
if (t == 1) {
cin >> u;
td[u] = i;
} else {
cin >> u >> v;
q[u].push_back({v, i});
}
}
for (int i = 1; i <= n; i++) {
if (us[i] == 0) {
for (int ii = 0; ii < 2 * N; ii++) {
st1[ii] = INF;
st2[ii] = INF;
}
int st = fcycle(i);
int c = i;
while (c != st) {
us[c] = 0;
c = a[c];
}
int now = st;
kk = 0;
while (us[now] == 1) {
us[now] = 2;
st1[N + kk] = td[now];
pos[now] = kk++;
now = a[now];
}
for (int j = N - 1; j > 0; j--)
st1[j] = min(st1[2 * j], st1[2 * j + 1]);
//cout << "st = " << st << endl;
//for (int j = 1; j <= n; j++) cout << us[j] << " "; cout << endl;
//for (int j = 1; j < 2 * N; j++) cout << st1[j] << " "; cout << endl;
now = st;
do {
incycle = now;
dfs(now, 0);
now = a[now];
} while (now != st);
c = st;
int k = 0;
while (a[c] != st) {
us[c] = 3;
st1[N + k] = INF;
k++;
c = a[c];
}
for (int j = N - 1; j > 0; j--)
st1[j] = min(st1[2 * j], st1[2 * j + 1]);
}
}
sort(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++)
cout << ans[i].second << endl;
return 0;
}
Compilation message
specialg.cpp: In function 'void dfs(int, int)':
specialg.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < q[x].size(); j++) {
~~^~~~~~~~~~~~~
specialg.cpp:85:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < g[x].size(); i++) {
~~^~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:191:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
7288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
