oj.uz

Submission #4753

# Submission time Handle Problem Language Result Execution time Memory
4753 2013-12-28T09:52:33 Z ainta Special graph (IZhO13_specialg) C++
85 / 100
 76 ms 11360 KB 
#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] || !w[i]){
			if(w[i])E[w[i]].push_back(i);
		}
		v[i] = 0;
	}
	cnt = 0;
	for (i = 1; i <= n; i++){
		if (Cyc[i][0])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
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9128 KB Output isn't correct
2 Correct 4 ms 9128 KB Output is correct
3 Correct 4 ms 9128 KB Output is correct
4 Incorrect 0 ms 9128 KB Output isn't correct
5 Incorrect 4 ms 9128 KB Output isn't correct
6 Correct 8 ms 9128 KB Output is correct
7 Correct 8 ms 9128 KB Output is correct
8 Correct 12 ms 9128 KB Output is correct
9 Correct 12 ms 9128 KB Output is correct
10 Correct 8 ms 9128 KB Output is correct
11 Correct 68 ms 9152 KB Output is correct
12 Correct 56 ms 10344 KB Output is correct
13 Correct 76 ms 10844 KB Output is correct
14 Correct 52 ms 10120 KB Output is correct
15 Correct 64 ms 10380 KB Output is correct
16 Correct 64 ms 10360 KB Output is correct
17 Correct 68 ms 11360 KB Output is correct
18 Correct 72 ms 11360 KB Output is correct
19 Correct 68 ms 11360 KB Output is correct
20 Correct 76 ms 9128 KB Output is correct