#include <cstdio>
#include <vector>
#include <cstring>
//FILE *fin = fopen("specialg.in", "r"), *fout = fopen("specialg.out", "w");
#define fin stdin
#define fout stdout
#define MAXN 100000
std::vector < int > g[MAXN + 1];
int viz[MAXN + 1], unde[MAXN + 1], l[MAXN + 1], r[MAXN + 1], t[MAXN + 1];
int *aib[2 * MAXN + 1], h[MAXN + 1], k, ciclu[MAXN + 1], pozitie[MAXN + 1];
int lungime[2 * MAXN + 1], lider, care[2 * MAXN + 1], cate[2 * MAXN + 1];
inline void updateAib(int v[], int n, int p, int add) {
while (p <= n) {
v[p] += add;
p += p & (-p);
}
}
inline int queryAib(int v[], int p) {
int ans = 0;
while (p > 0) {
ans += v[p];
p -= p & (-p);
}
return ans;
}
inline void update(int x) {
if (ciclu[x])
updateAib(aib[ciclu[x]], lungime[ciclu[x]], pozitie[x], 1);
else
updateAib(aib[unde[x]], cate[unde[x]], l[x], 1), updateAib(aib[unde[x]], cate[unde[x]], r[x], -1);
}
int query(int x, int y) {
if (ciclu[x]) {
if (ciclu[y] != ciclu[x])
return -1;
if (pozitie[x] <= pozitie[y]) {
if (queryAib(aib[ciclu[x]], pozitie[y] - 1) - queryAib(aib[ciclu[x]], pozitie[x] - 1) > 0)
return -1;
else
return pozitie[y] - pozitie[x];
} else {
if (queryAib(aib[ciclu[x]], lungime[ciclu[x]]) - queryAib(aib[ciclu[x]], pozitie[x] - 1) + queryAib(aib[ciclu[x]], pozitie[y] - 1) > 0)
return -1;
else
return lungime[ciclu[x]] - pozitie[x] + pozitie[y];
}
} else if (ciclu[y]) {
int u = query(care[unde[x]], y);
if (u == -1)
return -1;
if (queryAib(aib[unde[x]], l[x]) > 0)
return -1;
return h[x] + u;
} else if (l[y] <= l[x] && r[x] <= r[y] && unde[x] == unde[y] && queryAib(aib[unde[x]], l[x]) - queryAib(aib[unde[x]], l[y]) == 0)
return h[x] - h[y];
else
return -1;
}
void dfs(int x) {
viz[x] = 2;
unde[x] = lider;
l[x] = ++k;
for (auto &y : g[x]) {
if (viz[y] != 2) {
h[y] = h[x] + 1;
dfs(y);
}
}
r[x] = ++k;
}
int main() {
int n;
fscanf(fin, "%d", &n);
for (int i = 1; i <= n; i++) {
fscanf(fin, "%d", &t[i]);
if (t[i] == 0)
t[i] = i;
g[t[i]].push_back(i);
}
int nr = 0;
for (int i = 1; i <= n; i++) {
if (viz[i] == 0) {
int x = i;
while (viz[x] == 0) {
viz[x] = 1;
x = t[x];
}
nr++;
int poz = 0;
while (viz[x] == 1) {
viz[x] = 2;
ciclu[x] = nr;
poz++;
pozitie[x] = poz;
x = t[x];
}
lungime[nr] = poz;
aib[nr] = new int[lungime[nr] + 1];
memset(aib[nr], 0, sizeof(int) * (lungime[nr] + 1));
do {
nr++;
lider = nr;
care[nr] = x;
k = 0;
dfs(x);
cate[nr] = k;
aib[nr] = new int[k + 1];
memset(aib[nr], 0, sizeof(int) * (k + 1));
x = t[x];
} while (pozitie[x] != 1);
}
}
int q;
fscanf(fin, "%d", &q);
for (; q; q--) {
int t;
fscanf(fin, "%d", &t);
if (t == 1) {
int x;
fscanf(fin, "%d", &x);
update(x);
} else {
int x, y;
fscanf(fin, "%d%d", &x, &y);
fprintf(fout, "%d\n", query(x, y));
}
}
fclose(fin);
fclose(fout);
return 0;
}
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:82:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &n);
~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:85:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &t[i]);
~~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp:128:11: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &q);
~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:132:15: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &t);
~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:136:19: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d", &x);
~~~~~~^~~~~~~~~~~~~~~
specialg.cpp:141:19: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(fin, "%d%d", &x, &y);
~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2808 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2936 KB |
Output is correct |
| 3 |
Correct |
6 ms |
2936 KB |
Output is correct |
| 4 |
Correct |
8 ms |
2936 KB |
Output is correct |
| 5 |
Correct |
6 ms |
2808 KB |
Output is correct |
| 6 |
Correct |
12 ms |
3320 KB |
Output is correct |
| 7 |
Correct |
12 ms |
3192 KB |
Output is correct |
| 8 |
Correct |
12 ms |
3192 KB |
Output is correct |
| 9 |
Correct |
12 ms |
3192 KB |
Output is correct |
| 10 |
Correct |
19 ms |
3192 KB |
Output is correct |
| 11 |
Correct |
74 ms |
16120 KB |
Output is correct |
| 12 |
Correct |
68 ms |
9976 KB |
Output is correct |
| 13 |
Correct |
73 ms |
11896 KB |
Output is correct |
| 14 |
Correct |
63 ms |
9180 KB |
Output is correct |
| 15 |
Correct |
71 ms |
10360 KB |
Output is correct |
| 16 |
Correct |
76 ms |
10104 KB |
Output is correct |
| 17 |
Correct |
90 ms |
13912 KB |
Output is correct |
| 18 |
Correct |
80 ms |
13916 KB |
Output is correct |
| 19 |
Correct |
83 ms |
13944 KB |
Output is correct |
| 20 |
Correct |
74 ms |
16092 KB |
Output is correct |
