Submission #4754

#	Time	Username	Problem	Language	Result	Execution time	Memory
4754		ainta	Special graph (IZhO13_specialg)	C++98	100 / 100	80 ms	11360 KiB

specialg

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
#define N_ 100100
vector<int>E[N_];
int n, Q, w[N_], renum[N_], Cyc[N_][2], C, SZ[N_], v[N_], ed[N_], cnt, par[N_], Dep[N_], pp[N_], RR[N_];
bool Iscyc[N_];
struct Query{
	int a, b, c;
}q[N_];
void DFS(int a, int P){
	int i;
	pp[a] = P;
	renum[a] = ++cnt;
	for (i = 0; i < E[a].size(); i++){
		Dep[E[a][i]] = Dep[a] + 1;
		DFS(E[a][i], P);
	}
	ed[renum[a]] = cnt;
}
int find(int a){
	if (a == par[a])return a;
	return par[a] = find(par[a]);
}
void Link(int a, int b){
	int x = find(a), y = find(b);
	if (x == y){
		Iscyc[Cyc[x][0]] = true;
		return;
	}
	par[x] = y;
	find(a);
}
int dis(int x, int y){
	int P = find(x), cc, dx, dy;
	if (P != find(y))return -1;
	if (renum[y] < renum[x] && ed[renum[y]] >= renum[x])return Dep[x] - Dep[y];
	cc = Cyc[y][0];
	if (!cc)return -1;
	if (Iscyc[cc])return (Cyc[y][1] - Cyc[pp[x]][1] + SZ[cc]) % SZ[cc] + Dep[x];
	dx = (Cyc[P][1] - Cyc[pp[x]][1] + SZ[cc]) % SZ[cc];
	dy = (Cyc[P][1] - Cyc[y][1] + SZ[cc]) % SZ[cc];
	if (dy > dx)return -1;
	else return dx - dy + Dep[x];
}
int main()
{
	int x, t, c, i, y;
	scanf("%d", &n);
	for (i = 1; i <= n; i++){
		scanf("%d", &w[i]);
	}
	for (i = 1; i <= n; i++){
		x = i;
		t = cnt;
		while (x && !v[x]){
			v[x] = ++cnt;
			x = w[x];
		}
		if (x && v[x]>t){
			c = 0;
			t = x;
			Cyc[x][0] = ++C, Cyc[x][1] = c++;
			while (w[x] != t){
				x = w[x];
				Cyc[x][0] = C, Cyc[x][1] = c++;
			}
			SZ[C] = c;
		}
	}
	for (i = 1; i <= n; i++){
		if (!Cyc[i][0]){
			if(w[i])E[w[i]].push_back(i);
		}
		v[i] = 0;
	}
	cnt = 0;
	for (i = 1; i <= n; i++){
		if (Cyc[i][0] || !w[i])DFS(i, i);
		par[i] = i;
	}
	scanf("%d", &Q);
	for (i = 0; i < Q; i++){
		scanf("%d%d", &q[i].a, &q[i].b);
		if (q[i].a == 2)scanf("%d", &q[i].c);
		else v[q[i].b] = 1;
	}
	for (i = 1; i <= n; i++){
		if(!v[i] && w[i]) Link(i, w[i]);
	}
	cnt = 0;
	for (i = Q - 1; i >= 0; i--){
		if (q[i].a == 1){
			Link(q[i].b, w[q[i].b]);
			continue;
		}
		x = q[i].b, y = q[i].c;
		RR[cnt++] = dis(x, y);
	}
	for (i = cnt - 1; i >= 0; i--)printf("%d\n", RR[i]);
}

• Subtask 1: 100 / 100