Submission #5116

#	Time	Username	Problem	Language	Result	Execution time	Memory
5116		cki86201	Special graph (IZhO13_specialg)	C++98	100 / 100	92 ms	13704 KiB

specialg

#include<stdio.h>

const int N_ = 100010;
const int T_ = 1<<17;

int st[N_], en[N_<<1], nxt[N_<<1];
inline void addE(int s,int e,int c){nxt[c]=st[s],st[s]=c,en[c]=e;}
int ind[N_], p[N_], er[N_];
int N, M;
int S[N_], D[N_], U[N_], dep[N_], ns = 1;
int Que[N_];
int cn[N_], us[N_], ue[N_], nc;
int qua[N_][3];
int ans[N_], len;
int T[1<<18];

struct UnF{
	int p[N_], w[N_];
	void init(){for(int i=1;i<=N;i++)p[i] = i, w[i] = 1;}
	int Find(int x){
		if(x == p[x])return x;
		return p[x] = Find(p[x]);
	}
	void Union(int x,int y){
		x = Find(x), y = Find(y);
		if(x==y)return;
		else if(w[x]<w[y])p[x] = y, w[y] += w[x];
		else p[y] = x, w[x] += w[y];
	}
}uf;

void update(int x)
{
	x += T_;
	while(x)T[x]++, x>>=1;
}

bool read(int a,int b)
{
	a += T_, b += T_;
	int cnt = 0, save = b-a+1;
	while(a<=b){
		if(a&1)cnt += T[a];
		if(!(b&1))cnt += T[b];
		a = (a+1)>>1;
		b = (b-1)>>1;
	}
	return cnt == save;
}

void pushup()
{
	int i;
	int *fr = Que, *re = Que;
	for(i=1;i<=N;i++)if(!ind[i])*fr++ = i;
	while(fr!=re){
		int t = *re++;
		ind[p[t]]--;
		if(!ind[p[t]])*fr++ = p[t];
	}
}

inline bool c_ances(int x,int y){return S[x]<=D[y]&&D[y]<=D[x];}

void pushdown(int x,int f)
{
	S[x] = ns;
	U[x] = f;
	for(int i=st[x];i;i=nxt[i])
		if(!ind[en[i]] && !S[en[i]]){
			dep[en[i]] = dep[x] + 1;
			pushdown(en[i],f);
		}
	D[x] = ns++;
}

void cyc(int x,int s)
{
	pushdown(x,x);
	us[x] = s;
	cn[x] = ++nc;
	if(!cn[p[x]])cyc(p[x],s);
	ue[x] = nc;
}

int solve(int a,int b)
{
	if(uf.Find(a) != uf.Find(b))return -1;
	if(c_ances(b,a))return dep[a] - dep[b];
	if(!ind[b])return -1;
	int ret = dep[a];
	a = U[a];
	if(!ind[a])return -1;
	if(ue[a] < cn[b] || ue[b] < cn[a])return -1;
	if(cn[a] < cn[b] && read(cn[a],cn[b]-1))return ret + cn[b] - cn[a];
	if(cn[a] > cn[b] && read(cn[a],ue[a]) && read(us[a],cn[b]-1))return ret + 1 + ue[a] - us[a] - cn[a] + cn[b];
	return -1;
}

int main()
{
	scanf("%d",&N);
	int i;
	for(i=1;i<=N;i++){
		scanf("%d",p+i);
		if(p[i])addE(i,p[i],i<<1), addE(p[i],i,i<<1|1), ind[p[i]]++;
	}
	pushup();
	for(i=1;i<=N;i++)if(ind[i] && !cn[i])cyc(i,nc+1);
	for(i=1;i<=N;i++)if(!p[i])pushdown(i,i);
	scanf("%d",&M);
	for(i=1;i<=M;i++){
		scanf("%d%d",qua[i],qua[i]+1);
		if(qua[i][0] == 2)scanf("%d",qua[i]+2);
		else er[qua[i][1]] = i;
	}
	uf.init();
	for(i=1;i<=N;i++)if(p[i] && !er[i]){
		if(ind[i])update(cn[i]);
		uf.Union(i,p[i]);
	}
	for(i=M;i;i--){
		if(qua[i][0] == 1){
			uf.Union(qua[i][1],p[qua[i][1]]);
			if(ind[qua[i][1]])update(cn[qua[i][1]]);
		}
		else ans[len++] = solve(qua[i][1],qua[i][2]);
	}
	for(i=len-1;i>=0;i--)printf("%d\n",ans[i]);
	return 0;
}

• Subtask 1: 100 / 100