#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;
struct DisjointSet {
vector<int> parent, rnk;
DisjointSet(): parent(), rnk() { }
void resize(uint size) {
parent.resize(size+1);
rnk.resize(size+1, 1);
for(uint i = 1; i <= size; i++) parent[i] = i;
}
int group (int u) {
int ret = u;
while(ret != parent[ret]) ret = parent[ret];
while(u != ret) {
int p = parent[u];
parent[u] = ret;
u = p;
}
return ret;
}
bool merge (int u, int v) {
int a = group(u);
int b = group(v);
if(a == b) return false;
if(rnk[a] > rnk[b]) swap(a, b);
else if(rnk[a] == rnk[b]) ++rnk[b];
parent[a] = b;
return true;
}
};
const int lgN_ = 17, N_ = 100005;
const int Q_ = 100005;
int N; // 노드 수
int Next[lgN_][N_]; // Next[k, i]: i에서 2^k만큼 갔을 때 노드 번호
vector<int> Rev[N_]; // reverse graph
int Level[N_], Root[N_];
int Q;
pii Query[Q_];
bool deleted[N_];
int CYCN;
int cycle[N_], cycle_wh[N_], cycle_length[N_];
set<pii> cycle_group[N_];
DisjointSet component;
vector<int> result;
void input() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d", &Next[0][i]);
scanf("%d", &Q);
for(int i = 1; i <= Q; i++) {
int q; scanf("%d", &q);
if(q == 1) scanf("%d", &Query[i].first), Query[i].second = -1, deleted[Query[i].first] = true;
else scanf("%d%d", &Query[i].first, &Query[i].second);
}
}
void fillNext() {
for(int k = 1; k < lgN_; k++)
for(int i = 1; i <= N; i++) {
int x = Next[k - 1][i];
if(x == 0) continue;
Next[k][i] = Next[k - 1][x];
}
}
int go (int u, int len) {
for(int k = 0; k < lgN_; k++) {
if(u > 0 && (len & (1<<k))) u = Next[k][u];
}
return u;
}
void mergeComponent() {
component.resize(N);
for(int u = 1; u <= N; u++) {
int v = Next[0][u];
if(v > 0 && !deleted[u]) component.merge(u, v);
}
}
void findCycle() {
mergeComponent();
vector<int> pth;
vector<bool> visited(N+1);
for(int s = 1; s <= N; s++) if(!cycle[s]) {
pth.clear();
int last = -1;
for(int u = s; !visited[u] && u > 0; ) {
pth.push_back(u);
visited[u] = true;
u = Next[0][u];
last = u;
}
if(last > 0) {
int found_x = -1;
for(int i = 0; i < pth.size(); i++) {
if(pth[i] == last) found_x = i, ++CYCN;
if(found_x >= 0) cycle[pth[i]] = CYCN, cycle_wh[pth[i]] = i - found_x,
++cycle_length[CYCN];
}
int last = -1, first = -1;
int delnd = -1;
for(int i = found_x; i < pth.size(); i++) {
int u = pth[i];
int v = Next[0][u];
if(deleted[u]) delnd = i - found_x;
if(component.group(u) != component.group(v)) {
if(i+1 == pth.size() && first >= 0) cycle_group[CYCN].insert(pii(0, first));
if(last >= 0) cycle_group[CYCN].insert(pii(last+1, i-found_x));
else first = i-found_x;
last = i-found_x;
}else {
if(i+1 == pth.size()) {
if(first >= 0) {
if(first < last+1) first += cycle_length[CYCN];
cycle_group[CYCN].insert(pii(last+1, first));
}else if(delnd >= 0) { // 모두 선 하나로 연결되어 있음
int s = (delnd + 1) % cycle_length[CYCN];
cycle_group[CYCN].insert(pii(s, s + cycle_length[CYCN] - 1));
}
}
}
}
}
}
}
void fillLevel() {
for(int u = 1; u <= N; u++)
if(Next[0][u] > 0) Rev[Next[0][u]].push_back(u);
queue<int> que;
for(int s = 1; s <= N; s++) if(cycle[s] || Next[0][s] == 0) {
while(!que.empty()) que.pop();
que.push(s); que.push(-1); Root[s] = s;
while(!que.empty()) {
int u = que.front(); que.pop();
int p = que.front(); que.pop();
for(int e = 0; e < Rev[u].size(); e++) {
int v = Rev[u][e];
if(v != p && !cycle[v]) {
Level[v] = Level[u] + 1;
Root[v] = s;
que.push(v); que.push(u);
}
}
}
}
}
void solveQuery() {
for(int q = Q; q > 0; q--) {
int u = Query[q].first, v = Query[q].second;
if(v == -1) {
v = Next[0][u];
component.merge(u, v);
int c = cycle[u];
deleted[u] = 0;
if(c > 0) {
set<pii>& gr = cycle_group[c];
if(gr.size() <= 1) {
gr.clear();
}else {
set<pii>::iterator itv = gr.lower_bound( pii(cycle_wh[v], cycle_wh[v]) );
set<pii>::iterator itu = itv;
if(itu == gr.begin()) itu = gr.end();
--itu;
int ua = itu->first, ub = itu->second;
int va = itv->first, vb = itv->second;
gr.erase(itu);
gr.erase(itv);
if(vb < ua) vb += cycle_length[c];
gr.insert( pii(ua, vb) );
}
}
}else {
int ret = 0, a = u, b = v;
if(component.group(u) == component.group(v)) {
bool is_u_cycle = (cycle[u] > 0);
bool is_v_cycle = (cycle[v] > 0);
if(!is_u_cycle && !is_v_cycle) {
int len = Level[u] - Level[v];
if(len >= 0 && go(u, len) == v) ret = len;
}else if(!is_u_cycle && is_v_cycle) {
int len = Level[u] - Level[Root[u]];
if(len >= 0 && go(u, len) == Root[u]) ret = len;
u = Root[u]; is_u_cycle = true;
}
if(is_u_cycle && is_v_cycle) {
if(cycle_group[cycle[u]].empty()) {
int len = cycle_wh[v] - cycle_wh[u];
if(len < 0) len += cycle_length[cycle[u]];
ret += len;
}else {
int uw1 = cycle_wh[u], uw2 = uw1 + cycle_length[cycle[u]];
set<pii>& gr = cycle_group[cycle[u]];
set<pii>::iterator it1 = gr.lower_bound ( pii(uw1, uw1) );
if(it1 == gr.end()) it1--;
while(it1 != gr.end() && !(it1->first <= uw1 && uw1 <= it1->second) && it1->second >= uw1) if(it1 == gr.begin()) it1 = gr.end(); else it1--;
if(it1 != gr.end() && !(it1->first <= uw1 && uw1 <= it1->second)) it1 = gr.end();
set<pii>::iterator it2 = gr.lower_bound ( pii(uw2, uw2) );
if(it2 == gr.end()) it2--;
while(it2 != gr.end() && !(it2->first <= uw2 && uw2 <= it2->second) && it2->second >= uw2) if(it2 == gr.begin()) it2 = gr.end(); else it2--;
if(it2 != gr.end() && !(it2->first <= uw2 && uw2 <= it2->second)) it2 = gr.end();
set<pii>::iterator it = (it1 != gr.end()) ? it1 : it2;
if(it == gr.end()) ret = -1;
else {
int uw = (it1 != gr.end()) ? uw1 : uw2;
if(it->first <= cycle_wh[v] && cycle_wh[v] <= it->second) {
if(cycle_wh[v] >= uw) ret += cycle_wh[v] - uw;
else ret = -1;
}else if(it->first <= cycle_wh[v] + cycle_length[cycle[u]] && cycle_wh[v] + cycle_length[cycle[u]] <= it->second) {
if(cycle_wh[v] + cycle_length[cycle[u]] >= uw) ret += cycle_wh[v] + cycle_length[cycle[u]] - uw;
else ret = -1;
}else {
ret = -1;
}
}
}
}
}
if(a == b) ret = 0;
else if(ret == 0) ret = -1;
result.push_back(ret);
}
}
}
void output() {
for(int i = (int)result.size() - 1; i >= 0; i--) printf("%d\n", result[i]);
}
int main() {
int i;
input();
fillNext();
findCycle();
fillLevel();
solveQuery();
output();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
17756 KB |
Output is correct |
| 2 |
Correct |
0 ms |
17756 KB |
Output is correct |
| 3 |
Correct |
4 ms |
17756 KB |
Output is correct |
| 4 |
Correct |
4 ms |
17916 KB |
Output is correct |
| 5 |
Correct |
8 ms |
17756 KB |
Output is correct |
| 6 |
Correct |
8 ms |
17920 KB |
Output is correct |
| 7 |
Correct |
12 ms |
17924 KB |
Output is correct |
| 8 |
Correct |
12 ms |
17932 KB |
Output is correct |
| 9 |
Correct |
8 ms |
17928 KB |
Output is correct |
| 10 |
Correct |
8 ms |
17936 KB |
Output is correct |
| 11 |
Correct |
80 ms |
22688 KB |
Output is correct |
| 12 |
Correct |
76 ms |
20400 KB |
Output is correct |
| 13 |
Correct |
84 ms |
21316 KB |
Output is correct |
| 14 |
Correct |
72 ms |
20152 KB |
Output is correct |
| 15 |
Correct |
80 ms |
20508 KB |
Output is correct |
| 16 |
Correct |
76 ms |
20440 KB |
Output is correct |
| 17 |
Correct |
92 ms |
22008 KB |
Output is correct |
| 18 |
Correct |
84 ms |
22004 KB |
Output is correct |
| 19 |
Correct |
88 ms |
22004 KB |
Output is correct |
| 20 |
Correct |
84 ms |
22692 KB |
Output is correct |
