oj.uz

Submission #491186

# Submission time Handle Problem Language Result Execution time Memory
491186 2021-11-30T17:12:49 Z rainboy Pastiri (COI20_pastiri) C
100 / 100
 667 ms 64912 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	500000

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 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 dd[N], ta[N], tb[N], qu[N], n, head, cnt; char visited[N];

void dfs_(int i) {
	int o;

	if (visited[i] == 1)
		return;
	if (dd[i] == 0 && visited[i] == 0)
		update(ta[i], n, -1);
	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (dd[j] == dd[i] - 1)
			dfs_(j);
	}
}

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

	ta[i] = time++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs(i, j);
	}
	tb[i] = time;
	if (dd[i] == 0 && visited[i] == -1)
		visited[i] = 0, update(ta[i], n, 1);
	if ((p == -1 || dd[i] != dd[p] - 1) && query(tb[i] - 1) - query(ta[i] - 1) > 0)
		qu[cnt++] = i, dfs_(i);
}

int main() {
	int k, h, i, j;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		dd[i] = n;
	head = cnt = 0;
	while (k--) {
		scanf("%d", &i), i--;
		dd[i] = 0, qu[head + cnt++] = i;
	}
	while (cnt) {
		int d, o;

		i = qu[cnt--, head++], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (dd[j] > d)
				dd[j] = d, qu[head + cnt++] = j;
		}
	}
	memset(visited, -1, n * sizeof *visited);
	dfs(-1, 0);
	printf("%d\n", cnt);
	for (h = 0; h < cnt; h++)
		printf("%d ", qu[h] + 1);
	printf("\n");
	return 0;
}

Compilation message

pastiri.c: In function 'append':
pastiri.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
pastiri.c: In function 'main':
pastiri.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
pastiri.c:79:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
pastiri.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d", &i), i--;
      |   ^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 61456 KB Output is correct
2 Correct 198 ms 63040 KB Output is correct
3 Correct 198 ms 63148 KB Output is correct
4 Correct 249 ms 64912 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 2 ms 676 KB Output is correct
3 Correct 448 ms 36888 KB Output is correct
4 Correct 461 ms 41600 KB Output is correct
5 Correct 565 ms 37000 KB Output is correct
6 Correct 667 ms 39704 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 424 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 33112 KB Output is correct
2 Correct 500 ms 39744 KB Output is correct
3 Correct 491 ms 41284 KB Output is correct
4 Correct 461 ms 38596 KB Output is correct
5 Correct 348 ms 33512 KB Output is correct
6 Correct 500 ms 46792 KB Output is correct
7 Correct 541 ms 44568 KB Output is correct
8 Correct 492 ms 44072 KB Output is correct
9 Correct 523 ms 38728 KB Output is correct
10 Correct 485 ms 37264 KB Output is correct
11 Correct 447 ms 42116 KB Output is correct
12 Correct 402 ms 42912 KB Output is correct
13 Correct 384 ms 44432 KB Output is correct
14 Correct 381 ms 41160 KB Output is correct
15 Correct 38 ms 6676 KB Output is correct
16 Correct 488 ms 35680 KB Output is correct
17 Correct 324 ms 33928 KB Output is correct
18 Correct 412 ms 31860 KB Output is correct
19 Correct 491 ms 43900 KB Output is correct
20 Correct 529 ms 47652 KB Output is correct
21 Correct 480 ms 37512 KB Output is correct
22 Correct 458 ms 38524 KB Output is correct