#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 100005;
int n, q, ts, M[N], P[N], C[N];
int Nxt[N], Dt[N], Len[N], OK[N], Lz[N];
set < pair < int , int > > Q[N], S[N];
vector < pair < int , int > > Cyc;
vector < int > TP;
void DFSC(int v)
{
M[v] = ts;
if (!Nxt[v] || M[Nxt[v]] && M[Nxt[v]] != ts)
return ;
if (M[Nxt[v]])
Cyc.pb({Nxt[v], v});
else
P[Nxt[v]] = v, DFSC(Nxt[v]);
}
void DFS(int v)
{
M[v] = 1;
if (Nxt[v] && !C[Nxt[v]] && !M[Nxt[v]])
DFS(Nxt[v]);
TP.push_back(v);
}
inline void Push(int v)
{
auto it = Q[v].lower_bound({v, -1});
while (it != Q[v].end() && it->first == v)
{
OK[it->second] = 1;
Len[it->second] += Lz[v];
S[v].erase({it->second, it->first});
it = Q[v].erase(it);
}
while (S[v].size() && S[v].rbegin()->first > Dt[v])
{
Q[v].erase({S[v].rbegin()->second, S[v].rbegin()->first});
S[v].erase(*S[v].rbegin());
}
int nxt = Nxt[v];
if (S[v].size() > S[nxt].size())
{
S[nxt].swap(S[v]);
Q[nxt].swap(Q[v]);
Lz[v] ++; Lz[nxt] --;
swap(Lz[v], Lz[nxt]);
}
for (auto X : S[v])
{
S[nxt].insert(X);
Len[X.first] += 1 + Lz[v] - Lz[nxt];
}
for (auto X : Q[v])
Q[nxt].insert(X);
S[v].clear();
Q[v].clear();
Lz[v] = 0;
}
void FNL(int v)
{
M[v] ++;
Push(v);
if (M[Nxt[v]] < 2)
FNL(Nxt[v]);
}
int main()
{
scanf("%d", &n);
memset(Dt, 63, sizeof(Dt));
for (int i = 1; i <= n; i++)
{
scanf("%d", &Nxt[i]);
if (Nxt[i] == i) Nxt[i] = 0;
if (!Nxt[i]) Dt[i] = 0;
}
scanf("%d", &q);
for (int i = 1; i <= q; i++)
{
int tp, v, u;
scanf("%d%d", &tp, &v);
if (tp == 1)
Dt[v] = i, OK[i] = -1;
else
{
scanf("%d", &u);
S[v].insert({i, u});
Q[v].insert({u, i});
}
}
for (int i = 1; i <= n; i++)
if (!M[i])
ts ++, DFSC(i);
ts = 0;
for (auto X : Cyc)
{
++ ts;
int v = X.first, u = X.second;
while (u != v)
C[u] = ts, u = P[u];
C[v] = ts;
}
memset(M, 0, sizeof(M));
for (int i = 1; i <= n; i++)
if (!M[i]) DFS(i);
reverse(TP.begin(), TP.end());
for (int v : TP)
Push(v);
memset(M, 0, sizeof(M));
for (int i = 1; i <= n; i++)
if (C[i] && !M[i]) FNL(i);
for (int i = 1; i <= q; i++)
{
if (OK[i] == 0)
printf("-1\n");
if (OK[i] == 1)
printf("%d\n", Len[i]);
}
return 0;
}
Compilation message
specialg.cpp: In function 'void DFSC(int)':
specialg.cpp:13:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (!Nxt[v] || M[Nxt[v]] && M[Nxt[v]] != ts)
~~~~~~~~~~^~~~~~~~~~~~~~~~~~
specialg.cpp: In function 'int main()':
specialg.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
specialg.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Nxt[i]);
~~~~~^~~~~~~~~~~~~~~
specialg.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
specialg.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &tp, &v);
~~~~~^~~~~~~~~~~~~~~~~
specialg.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &u);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
11008 KB |
Output is correct |
| 2 |
Correct |
18 ms |
10880 KB |
Output is correct |
| 3 |
Correct |
16 ms |
11008 KB |
Output is correct |
| 4 |
Correct |
33 ms |
11640 KB |
Output is correct |
| 5 |
Correct |
21 ms |
10928 KB |
Output is correct |
| 6 |
Correct |
58 ms |
12920 KB |
Output is correct |
| 7 |
Correct |
56 ms |
12920 KB |
Output is correct |
| 8 |
Correct |
63 ms |
12920 KB |
Output is correct |
| 9 |
Correct |
58 ms |
12912 KB |
Output is correct |
| 10 |
Correct |
61 ms |
13008 KB |
Output is correct |
| 11 |
Correct |
434 ms |
28504 KB |
Output is correct |
| 12 |
Correct |
502 ms |
24828 KB |
Output is correct |
| 13 |
Correct |
428 ms |
25772 KB |
Output is correct |
| 14 |
Correct |
483 ms |
24652 KB |
Output is correct |
| 15 |
Correct |
500 ms |
25072 KB |
Output is correct |
| 16 |
Correct |
486 ms |
24948 KB |
Output is correct |
| 17 |
Correct |
454 ms |
26556 KB |
Output is correct |
| 18 |
Correct |
431 ms |
26644 KB |
Output is correct |
| 19 |
Correct |
435 ms |
26736 KB |
Output is correct |
| 20 |
Correct |
437 ms |
28348 KB |
Output is correct |
