#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
const int MAX = 100020, BIT_MAX = 17;
int n, to[MAX], numQuery, qType[MAX], qA[MAX], qB[MAX];
vector < int > children[MAX];
void input(){
scanf("%d", &n);
int i;
for(i = 1; i<=n; i++){
scanf("%d", &to[i]);
children[to[i]].push_back(i);
}
scanf("%d", &numQuery);
for(i = 0; i<numQuery; i++){
scanf("%d%d", &qType[i], &qA[i]);
if(qType[i] == 2) scanf("%d", &qB[i]);
}
}
int visited[MAX], cFull, cycleNum[MAX], cycleOrder[MAX], cycleSize[MAX];
int findCycle(int now, int visitNum){
visited[now] = visitNum;
if(visited[to[now]] == 0){
int t = findCycle(to[now], visitNum);
if(t){
cycleNum[now] = cFull;
cycleOrder[now] = cycleOrder[to[now]]+1;
} else {
cycleNum[now] = -abs(cycleNum[to[now]]);
cycleOrder[now] = cycleOrder[to[now]];
}
if(now == t) return 0;
else return t;
} else if(visited[to[now]] == visitNum){
cycleNum[now] = ++cFull;
cycleOrder[now] = 1;
return to[now];
} else {
cycleNum[now] = -abs(cycleNum[to[now]]);
cycleOrder[now] = cycleOrder[to[now]];
return 0;
}
}
int depth[MAX], p[20][MAX];
void calcDepth(int now){
int i;
for(i = 0; i<children[now].size(); i++){
int nextNum = children[now][i];
depth[nextNum] = depth[now]+1;
calcDepth(nextNum);
}
}
void init(){
int i, v = 1;
for(i = 1; i<=n; i++){
if(visited[i] == 0)
findCycle(i, v++);
}
for(i = 1; i<=n; i++){
if(cycleNum[i] < 0){
if(cycleNum[to[i]] == cycleNum[i]) p[0][i] = to[i];
else {
p[0][i] = i;
calcDepth(i);
}
} else {
cycleSize[cycleNum[i]]++;
p[0][i] = i;
}
}
int lvl = 1;
for(lvl = 1; lvl<=BIT_MAX; lvl++){
for(i = 1; i<=n; i++)
p[lvl][i] = p[lvl-1][p[lvl-1][i]];
}
}
int uf[MAX], firstCut[MAX];
bool cycleOK[MAX];
int getParent(int num){
if(uf[num] == num) return num;
return uf[num] = getParent(uf[num]);
}
void link(int a, int b){
if(getParent(a) == getParent(b)){
cycleOK[cycleNum[a]] = 1;
} else {
uf[getParent(a)] = getParent(b);
}
}
void cut(){
int i, tNext[MAX];
for(i = 1; i<=n; i++){
tNext[i] = to[i];
uf[i] = i;
}
for(i = 1; i<=cFull; i++)
cycleOK[i] = 1;
for(i = 0; i<numQuery; i++){
if(qType[i] == 1){
int cn = cycleNum[qA[i]];
if(cn > 0 && firstCut[cn] == 0){
firstCut[cn] = cycleOrder[qA[i]];
cycleOK[cn] = 0;
}
tNext[qA[i]] = 0;
}
}
for(i = 1; i<=n; i++){
if(tNext[i]){
link(i, tNext[i]);
}
}
}
int cycleDist(int f, int s){
int cn = cycleNum[f];
if(cycleOK[cn] ||
(cycleOrder[f] > cycleOrder[s]
? !(cycleOrder[f] >= firstCut[cn] && firstCut[cn] > cycleOrder[s])
: !(cycleOrder[f] >= firstCut[cn] || firstCut[cn] > cycleOrder[s]))){
int cs = cycleSize[cn];
return (cycleOrder[f]-cycleOrder[s]+cs) % cs;
} else return -1;
}
int res[MAX];
void solve(){
int i;
for(i = numQuery-1; i>=0; i--){
if(qType[i] == 1){
link(qA[i], to[qA[i]]);
} else {
res[i] = -1;
int f = qA[i], s = qB[i];
if(f == s) res[i] = 0;
else if(getParent(f) == getParent(s)){
if(cycleNum[s] > 0){
if(cycleNum[f] == cycleNum[s]){
//사이클 -> 사이클
res[i] = cycleDist(f, s);
} else if(cycleNum[f] == -cycleNum[s]){
//트리 -> 사이클
int t = cycleDist(to[p[BIT_MAX][f]], s);
if(t != -1)
res[i] = depth[f]+1 + t;
}
} else {
if(cycleNum[f] == cycleNum[s] && cycleOrder[f] == cycleOrder[s] && depth[s] < depth[f]){
//트리 -> 트리
int dist = depth[f]-depth[s];
int t;
for(t = 0; t<=BIT_MAX; t++){
if(dist & (1<<t)){
f = p[t][f];
}
}
if(f == s)
res[i] = dist;
}
}
}
}
}
for(i = 0; i<numQuery; i++){
if(qType[i] == 2){
printf("%d\n", res[i]);
}
}
}
int main(){
input();
init();
cut();
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
16420 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
16420 KB |
Output isn't correct |
| 3 |
Incorrect |
0 ms |
16420 KB |
Output isn't correct |
| 4 |
Incorrect |
0 ms |
16420 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
16424 KB |
Output isn't correct |
| 6 |
Incorrect |
12 ms |
16420 KB |
Output isn't correct |
| 7 |
Incorrect |
12 ms |
16420 KB |
Output isn't correct |
| 8 |
Incorrect |
8 ms |
16424 KB |
Output isn't correct |
| 9 |
Correct |
12 ms |
16424 KB |
Output is correct |
| 10 |
Incorrect |
4 ms |
16420 KB |
Output isn't correct |
| 11 |
Correct |
80 ms |
22196 KB |
Output is correct |
| 12 |
Incorrect |
68 ms |
18256 KB |
Output isn't correct |
| 13 |
Correct |
80 ms |
19108 KB |
Output is correct |
| 14 |
Incorrect |
68 ms |
18004 KB |
Output isn't correct |
| 15 |
Correct |
76 ms |
18444 KB |
Output is correct |
| 16 |
Correct |
76 ms |
18276 KB |
Output is correct |
| 17 |
Correct |
76 ms |
19972 KB |
Output is correct |
| 18 |
Incorrect |
84 ms |
19968 KB |
Output isn't correct |
| 19 |
Correct |
80 ms |
19968 KB |
Output is correct |
| 20 |
Correct |
72 ms |
22192 KB |
Output is correct |
