// #define DEBUG
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long llong;
int nei[300001], depth[300001], cycleSize[300001], cycleEnd[300001];
bool used[300001], inCycle[300001], okCycle[300001];
int DFS(int v, int dep = 0)
{
used[v] = true;
depth[v] = dep;
if (!nei[v])
return 0;
if (used[nei[v]])
{
inCycle[v] = true;
cycleEnd[v] = v;
cycleSize[v] = depth[v] - depth[nei[v]] + 1;
return cycleEnd[v];
}
cycleEnd[v] = DFS(nei[v], dep + 1);
if (cycleEnd[v])
{
inCycle[v] = true;
cycleSize[v] = cycleSize[nei[v]];
return cycleEnd[v];
}
return 0;
}
int par[300001], sz[300001], cyc[300001];
int Root(int v)
{
return par[v] == 0 ? v : par[v] = Root(par[v]);
}
void Union(int u, int v)
{
u = Root(u); v = Root(v);
if (sz[u] > sz[v])
swap(u, v);
sz[v] += sz[u];
cyc[v] += cyc[u];
if (cyc[v] == cycleSize[v])
okCycle[cycleEnd[v]] = true;
par[u] = v;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
set<int> roots;
for (int v = 1; v <= n; ++v)
roots.insert(v);
for (int v = 1; v <= n; ++v)
{
cin >> nei[v];
roots.erase(nei[v]);
}
for (int v: roots)
DFS(v);
for (int v = 1; v <= n; ++v)
if (!used[v])
DFS(v);
struct Q
{
int type;
int s, e, v;
};
int m;
cin >> m;
vector<Q> q(m);
set<int> notDel;
for (int i = 1; i <= n; ++i)
notDel.insert(i);
for (int i = 0; i < m; ++i)
{
cin >> q[i].type;
if (q[i].type == 1)
{
cin >> q[i].v;
notDel.erase(q[i].v);
}
else
cin >> q[i].s >> q[i].e;
}
for (auto x: notDel)
{
Q curQ;
curQ.type = 1;
curQ.v = x;
q.push_back(curQ);
}
m = q.size();
reverse(q.begin(), q.end());
vector<int> ans;
fill(sz, sz + n + 1, 1);
for (int i = 1; i <= n; ++i)
cyc[i] = inCycle[i];
for (int i = 0; i < q.size(); ++i)
{
if (q[i].type == 1)
Union(q[i].v, nei[q[i].v]);
else
{
int s = q[i].s, e = q[i].e;
if (i == 5)
cerr << s << ' ' << e << endl;
if (Root(s) == Root(e))
{
if (depth[s] <= depth[e])
ans.push_back(depth[e] - depth[s]);
else if (inCycle[s] && inCycle[e] && okCycle[cycleEnd[s]])
ans.push_back(cycleSize[cycleEnd[s]] - (depth[s] - depth[e]));
else
ans.push_back(-1);
}
else
ans.push_back(-1);
}
}
reverse(ans.begin(), ans.end());
for (int x: ans)
cout << x << ' ';
}
Compilation message
specialg.cpp: In function 'int main()':
specialg.cpp:104:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < q.size(); ++i)
~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
78 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
