Submission #636575

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636575	2022-08-29T15:27:56 Z	rainboy	Jail (JOI22_jail)	C	10 / 100	59 ms	16228 KB

jail

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	120000

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 dd[N], pp[N];

void dfs(int p, int i, int d) {
	int o;

	dd[i] = d, pp[i] = p;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs(i, j, d + 1);
	}
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int ii[2], jj[N];
		static char bb[N];
		int n, m, h, i, j, line, yes;

		scanf("%d", &n);
		for (i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
		line = 1;
		for (h = 0; h < n - 1; h++) {
			scanf("%d%d", &i, &j), i--, j--;
			if (i + 1 != j)
				line = 0;
			append(i, j), append(j, i);
		}
		dfs(-1, 0, 0);
		if (line) {
			scanf("%d", &m);
			memset(jj, -1, n * sizeof *jj);
			while (m--) {
				scanf("%d%d", &i, &j), i--, j--;
				jj[i] = j;
			}
			yes = 1;
			for (i = 0, j = -1; i < n; i++)
				if (jj[i] != -1) {
					if (j >= jj[i]) {
						yes = 0;
						break;
					}
					j = jj[i];
				}
			printf(yes ? "Yes\n" : "No\n");
		} else {
			memset(bb, 0, n * sizeof *bb);
			scanf("%d", &m);
			for (h = 0; h < m; h++) {
				scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
				i = ii[h], j = jj[h];
				while (i != j)
					if (dd[i] > dd[j])
						bb[i] |= 1 << h, i = pp[i];
					else
						bb[j] |= 1 << h, j = pp[j];
				bb[i] |= 1 << h;
			}
			printf(((bb[ii[0]] & 1 << 1) != 0 || (bb[jj[1]] & 1 << 0) != 0) && ((bb[ii[1]] & 1 << 0) != 0 || (bb[jj[0]] & 1 << 1) != 0) ? "No\n" : "Yes\n");
		}
	}
	return 0;
}

Compilation message

jail.c: In function 'append':
jail.c:12:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
jail.c: In function 'main':
jail.c:34:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
jail.c:40:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
jail.c:45:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
jail.c:52:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |    scanf("%d", &m);
      |    ^~~~~~~~~~~~~~~
jail.c:55:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d", &i, &j), i--, j--;
      |     ^~~~~~~~~~~~~~~~~~~~~
jail.c:70:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |    scanf("%d", &m);
      |    ^~~~~~~~~~~~~~~
jail.c:72:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	1944 KB	Output is correct
5	Correct	25 ms	3972 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	31 ms	4540 KB	Output is correct
10	Correct	34 ms	16200 KB	Output is correct
11	Correct	6 ms	852 KB	Output is correct
12	Correct	31 ms	4052 KB	Output is correct
13	Correct	41 ms	16184 KB	Output is correct
14	Correct	42 ms	16204 KB	Output is correct
15	Correct	43 ms	16228 KB	Output is correct
16	Correct	59 ms	16228 KB	Output is correct
17	Correct	44 ms	16212 KB	Output is correct
18	Correct	57 ms	16200 KB	Output is correct
19	Correct	47 ms	16192 KB	Output is correct
20	Correct	45 ms	16228 KB	Output is correct
21	Correct	54 ms	16224 KB	Output is correct
22	Correct	43 ms	16224 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	432 KB	Output is correct
7	Correct	2 ms	416 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	2 ms	436 KB	Output is correct
11	Correct	2 ms	432 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct

Subtask #3
0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	432 KB	Output is correct
7	Correct	2 ms	416 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	2 ms	436 KB	Output is correct
11	Correct	2 ms	432 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	432 KB	Output is correct
7	Correct	2 ms	416 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	2 ms	436 KB	Output is correct
11	Correct	2 ms	432 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	2 ms	468 KB	Output is correct
5	Correct	2 ms	468 KB	Output is correct
6	Correct	2 ms	432 KB	Output is correct
7	Correct	2 ms	416 KB	Output is correct
8	Correct	1 ms	468 KB	Output is correct
9	Correct	1 ms	468 KB	Output is correct
10	Correct	2 ms	436 KB	Output is correct
11	Correct	2 ms	432 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	308 KB	Output is correct
14	Incorrect	1 ms	212 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	212 KB	Output is correct
2	Incorrect	212 KB	Output isn't correct
3	Halted	0 KB	-

Subtask #7
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	11 ms	1944 KB	Output is correct
5	Correct	25 ms	3972 KB	Output is correct
6	Correct	1 ms	468 KB	Output is correct
7	Correct	1 ms	468 KB	Output is correct
8	Correct	2 ms	468 KB	Output is correct
9	Correct	31 ms	4540 KB	Output is correct
10	Correct	34 ms	16200 KB	Output is correct
11	Correct	6 ms	852 KB	Output is correct
12	Correct	31 ms	4052 KB	Output is correct
13	Correct	41 ms	16184 KB	Output is correct
14	Correct	42 ms	16204 KB	Output is correct
15	Correct	43 ms	16228 KB	Output is correct
16	Correct	59 ms	16228 KB	Output is correct
17	Correct	44 ms	16212 KB	Output is correct
18	Correct	57 ms	16200 KB	Output is correct
19	Correct	47 ms	16192 KB	Output is correct
20	Correct	45 ms	16228 KB	Output is correct
21	Correct	54 ms	16224 KB	Output is correct
22	Correct	43 ms	16224 KB	Output is correct
23	Correct	0 ms	212 KB	Output is correct
24	Correct	0 ms	212 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	2 ms	468 KB	Output is correct
27	Correct	2 ms	468 KB	Output is correct
28	Correct	2 ms	432 KB	Output is correct
29	Correct	2 ms	416 KB	Output is correct
30	Correct	1 ms	468 KB	Output is correct
31	Correct	1 ms	468 KB	Output is correct
32	Correct	2 ms	436 KB	Output is correct
33	Correct	2 ms	432 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	308 KB	Output is correct
36	Incorrect	1 ms	212 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

Submission #636575

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 0 / 16.0

Subtask #4 0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
0 / 16.0

Subtask #4
0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0