Submission #4754

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4754	2013-12-28T09:53:39 Z	ainta	Special graph (IZhO13_specialg)	C++	100 / 100	80 ms	11360 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9128 KB	Output is correct
2	Correct	0 ms	9128 KB	Output is correct
3	Correct	0 ms	9128 KB	Output is correct
4	Correct	4 ms	9128 KB	Output is correct
5	Correct	0 ms	9128 KB	Output is correct
6	Correct	8 ms	9128 KB	Output is correct
7	Correct	12 ms	9128 KB	Output is correct
8	Correct	8 ms	9128 KB	Output is correct
9	Correct	8 ms	9128 KB	Output is correct
10	Correct	12 ms	9128 KB	Output is correct
11	Correct	64 ms	9148 KB	Output is correct
12	Correct	68 ms	10344 KB	Output is correct
13	Correct	76 ms	10848 KB	Output is correct
14	Correct	68 ms	10120 KB	Output is correct
15	Correct	64 ms	10384 KB	Output is correct
16	Correct	68 ms	10356 KB	Output is correct
17	Correct	80 ms	11360 KB	Output is correct
18	Correct	64 ms	11360 KB	Output is correct
19	Correct	76 ms	11360 KB	Output is correct
20	Correct	64 ms	9128 KB	Output is correct