답안 #742215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
742215 2023-05-15T20:10:20 Z rainboy 특수한 그래프 (IZhO13_specialg) C
100 / 100
67 ms 15580 KB
#include <stdio.h>
#include <stdlib.h>

#define N	100000

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int rr[N], dd[N], ta[N], tb[N]; char visited[N];

void dfs(int i, int r, int d) {
	static int time;
	int o;

	if (visited[i] == 1)
		return;
	visited[i] = 1;
	ta[i] = time++;
	rr[i] = r, dd[i] = d;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j, r, d + 1);
	}
	tb[i] = time;
}

int ft[N];

void update(int i, int n, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int main() {
	static int pp[N];
	int n, m, i, j;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n; i++) {
		scanf("%d", &pp[i]), pp[i]--;
		if (pp[i] != -1)
			append(pp[i], i);
	}
	for (i = 0; i < n; i++) {
		if (visited[i])
			continue;
		j = i;
		while (pp[j] != -1 && !visited[j])
			visited[j] = -1, j = pp[j];
		dfs(j, j, 0);
	}
	scanf("%d", &m);
	while (m--) {
		int t, ans;

		scanf("%d", &t);
		if (t == 1) {
			scanf("%d", &i), i--;
			pp[i] = -1;
			update(ta[i], n, 1), update(tb[i], n, -1);
		} else {
			scanf("%d%d", &i, &j), i--, j--;
			if (ta[j] <= ta[i] && tb[i] <= tb[j])
				ans = query(ta[i]) - query(ta[j]) == 0 ? dd[i] - dd[j] : -1;
			else {
				if (query(ta[i]) > 0)
					ans = -1;
				else {
					ans = dd[i] + 1;
					if ((i = pp[rr[i]]) == -1 || ta[i] < ta[j] || ta[i] >= tb[j])
						ans = -1;
					else
						ans = query(ta[i]) - query(ta[j]) == 0 ? ans + dd[i] - dd[j] : -1;
				}
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

Compilation message

specialg.c: In function 'append':
specialg.c:11:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
specialg.c: In function 'main':
specialg.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
specialg.c:62:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
specialg.c:74:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  scanf("%d", &m);
      |  ^~~~~~~~~~~~~~~
specialg.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
specialg.c:80:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
specialg.c:84:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 432 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 8 ms 732 KB Output is correct
7 Correct 11 ms 720 KB Output is correct
8 Correct 8 ms 680 KB Output is correct
9 Correct 9 ms 688 KB Output is correct
10 Correct 8 ms 724 KB Output is correct
11 Correct 63 ms 15400 KB Output is correct
12 Correct 64 ms 8816 KB Output is correct
13 Correct 54 ms 11184 KB Output is correct
14 Correct 52 ms 7884 KB Output is correct
15 Correct 56 ms 9204 KB Output is correct
16 Correct 53 ms 8972 KB Output is correct
17 Correct 67 ms 13768 KB Output is correct
18 Correct 66 ms 13708 KB Output is correct
19 Correct 62 ms 13692 KB Output is correct
20 Correct 60 ms 15580 KB Output is correct