oj.uz

답안 #4752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4752 2013-12-28T09:44:13 Z ainta 특수한 그래프 (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

# 결과 실행 시간 메모리 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