oj.uz

답안 #5116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5116 2014-02-09T11:25:02 Z cki86201 특수한 그래프 (IZhO13_specialg) C++
100 / 100
 92 ms 13704 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 10704 KB Output is correct
2 Correct 0 ms 10704 KB Output is correct
3 Correct 0 ms 10704 KB Output is correct
4 Correct 4 ms 10704 KB Output is correct
5 Correct 0 ms 10704 KB Output is correct
6 Correct 12 ms 10704 KB Output is correct
7 Correct 12 ms 10704 KB Output is correct
8 Correct 12 ms 10704 KB Output is correct
9 Correct 12 ms 10704 KB Output is correct
10 Correct 4 ms 10704 KB Output is correct
11 Correct 80 ms 13704 KB Output is correct
12 Correct 68 ms 11488 KB Output is correct
13 Correct 80 ms 11804 KB Output is correct
14 Correct 68 ms 11364 KB Output is correct
15 Correct 68 ms 11532 KB Output is correct
16 Correct 72 ms 11508 KB Output is correct
17 Correct 92 ms 12136 KB Output is correct
18 Correct 80 ms 12144 KB Output is correct
19 Correct 80 ms 12144 KB Output is correct
20 Correct 84 ms 13704 KB Output is correct