oj.uz

Submission #527550

# Submission time Handle Problem Language Result Execution time Memory
527550 2022-02-17T15:33:30 Z rainboy 스파이 (JOI13_spy) C
100 / 100
 211 ms 20892 KB 
#include <stdio.h>
#include <stdlib.h>

#define N	2000

void append(int **ej, int *eo, 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 time;

void dfs(int **ej, int *eo, int *ta, int *tb, int i) {
	int o;

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

		dfs(ej, eo, ta, tb, j);
	}
	tb[i] = time;
}

int main() {
	static int *ej[2][N], eo[2][N], rr[2], ta[2][N], tb[2][N], aa[N + 1][N + 1];
	int n, m, h, i, j;

	scanf("%d%d", &n, &m);
	for (h = 0; h < 2; h++)
		for (i = 0; i < n; i++)
			ej[h][i] = (int *) malloc(2 * sizeof *ej[h][i]);
	for (j = 0; j < n; j++)
		for (h = 0; h < 2; h++) {
			scanf("%d", &i), i--;
			if (i == -1)
				rr[h] = j;
			else
				append(ej[h], eo[h], i, j);
		}
	for (h = 0; h < 2; h++)
		time = 0, dfs(ej[h], eo[h], ta[h], tb[h], rr[h]);
	while (m--) {
		scanf("%d%d", &i, &j), i--, j--;
		aa[ta[0][i]][ta[1][j]]++, aa[ta[0][i]][tb[1][j]]--;
		aa[tb[0][i]][ta[1][j]]--, aa[tb[0][i]][tb[1][j]]++;
	}
	for (i = 0; i < n; i++)
		for (j = 1; j < n; j++)
			aa[i][j] += aa[i][j - 1];
	for (j = 0; j < n; j++)
		for (i = 1; i < n; i++)
			aa[i][j] += aa[i - 1][j];
	for (i = 0; i < n; i++)
		printf("%d\n", aa[ta[0][i]][ta[1][i]]);
	return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1232 KB Output is correct
2 Correct 1 ms 1232 KB Output is correct
3 Correct 1 ms 1184 KB Output is correct
4 Correct 1 ms 1232 KB Output is correct
5 Correct 1 ms 1232 KB Output is correct
6 Correct 2 ms 1232 KB Output is correct
7 Correct 1 ms 1232 KB Output is correct
8 Correct 1 ms 1232 KB Output is correct
9 Correct 0 ms 208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16300 KB Output is correct
2 Correct 50 ms 16336 KB Output is correct
3 Correct 57 ms 16184 KB Output is correct
4 Correct 60 ms 16080 KB Output is correct
5 Correct 57 ms 16060 KB Output is correct
6 Correct 46 ms 16080 KB Output is correct
7 Correct 44 ms 16212 KB Output is correct
8 Correct 49 ms 16080 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 20648 KB Output is correct
2 Correct 141 ms 20620 KB Output is correct
3 Correct 148 ms 20632 KB Output is correct
4 Correct 160 ms 20892 KB Output is correct
5 Correct 188 ms 20484 KB Output is correct
6 Correct 129 ms 19920 KB Output is correct
7 Correct 194 ms 20524 KB Output is correct
8 Correct 211 ms 20728 KB Output is correct