oj.uz

Submission #482194

# Submission time Handle Problem Language Result Execution time Memory
482194 2021-10-23T15:19:44 Z rainboy Birmingham (COCI20_birmingham) C
70 / 70
 144 ms 9520 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 main() {
	static int dd[N], tt[N], qu[N];
	int n, m, q, k, h, i, j, d, t, head, cnt;

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

		i = qu[cnt--, head++], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (dd[j] > d)
				dd[j] = d, qu[head + cnt++] = j;
		}
	}
	for (i = 0; i < n; i++)
		printf("%d ", tt[dd[i]]);
	printf("\n");
	return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8752 KB Output is correct
2 Correct 81 ms 9212 KB Output is correct
3 Correct 80 ms 9520 KB Output is correct
4 Correct 64 ms 8368 KB Output is correct
5 Correct 80 ms 8524 KB Output is correct
6 Correct 88 ms 9376 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 9176 KB Output is correct
2 Correct 73 ms 9100 KB Output is correct
3 Correct 87 ms 9260 KB Output is correct
4 Correct 77 ms 9412 KB Output is correct
5 Correct 72 ms 9092 KB Output is correct
6 Correct 73 ms 8796 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 8836 KB Output is correct
2 Correct 115 ms 9364 KB Output is correct
3 Correct 99 ms 9516 KB Output is correct
4 Correct 92 ms 9392 KB Output is correct
5 Correct 61 ms 8660 KB Output is correct
6 Correct 73 ms 8832 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 8516 KB Output is correct
2 Correct 79 ms 9052 KB Output is correct
3 Correct 104 ms 9392 KB Output is correct
4 Correct 67 ms 8748 KB Output is correct
5 Correct 84 ms 8504 KB Output is correct
6 Correct 66 ms 8716 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8460 KB Output is correct
2 Correct 83 ms 8808 KB Output is correct
3 Correct 70 ms 8792 KB Output is correct
4 Correct 61 ms 8644 KB Output is correct
5 Correct 62 ms 8768 KB Output is correct
6 Correct 62 ms 8772 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 8600 KB Output is correct
2 Correct 61 ms 8912 KB Output is correct
3 Correct 64 ms 8748 KB Output is correct
4 Correct 66 ms 9028 KB Output is correct
5 Correct 88 ms 8644 KB Output is correct
6 Correct 70 ms 8864 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8832 KB Output is correct
2 Correct 57 ms 8332 KB Output is correct
3 Correct 75 ms 9412 KB Output is correct
4 Correct 60 ms 8612 KB Output is correct
5 Correct 66 ms 8900 KB Output is correct
6 Correct 73 ms 9412 KB Output is correct