oj.uz

Submission #4752

# Submission time Handle Problem Language Result Execution time Memory
4752 2013-12-28T09:44:13 Z ainta Special graph (IZhO13_specialg) C++
85 / 100
 84 ms 11364 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]){
			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 4 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 12 ms 9128 KB Output is correct
8 Correct 8 ms 9128 KB Output is correct
9 Correct 12 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 10340 KB Output is correct
13 Correct 68 ms 10848 KB Output is correct
14 Correct 56 ms 10120 KB Output is correct
15 Correct 72 ms 10384 KB Output is correct
16 Correct 64 ms 10356 KB Output is correct
17 Correct 84 ms 11360 KB Output is correct
18 Correct 76 ms 11364 KB Output is correct
19 Correct 80 ms 11364 KB Output is correct
20 Correct 60 ms 9128 KB Output is correct