Submission #636584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
636584	2022-08-29T15:55:37 Z	rainboy	Jail (JOI22_jail)	C	5 / 100	75 ms	16240 KB

jail

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

#define N	120000

int *ej[N], eo[N], *eh[N], eo_[N], fo_[N];

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

void dfs1(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)
			dfs1(i, j, d + 1);
	}
}

void dfs2(int h) {
	int o;

	if (fo_[h])
		return;
	fo_[h] = -1;
	for (o = eo_[h]; o--; ) {
		int h_ = eh[h][o];

		fo_[h_]--, dfs2(h_);
	}
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int ii[N], jj[N], hhi[N], hhj[N];
		int n, m, h, 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(ej, eo, i, j), append(ej, eo, j, i);
		}
		dfs1(-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 {
			scanf("%d", &m);
			memset(hhi, -1, n * sizeof *hhi), memset(hhj, -1, n * sizeof *hhj);
			for (h = 0; h < m; h++) {
				scanf("%d%d", &ii[h], &jj[h]), ii[h]--, jj[h]--;
				hhi[ii[h]] = hhj[jj[h]] = h;
			}
			for (h = 0; h < m; h++)
				eh[h] = (int *) malloc(2 * sizeof *eh[h]), eo_[h] = 0, fo_[h] = 0;
			for (h = 0; h < m; h++) {
				i = ii[h], j = jj[h];
				while (i != j)
					if (dd[i] > dd[j]) {
						h_ = hhi[i];
						if (h_ != -1 && h_ != h)
							append(eh, eo_, h_, h), fo_[h]++;
						h_ = hhj[i];
						if (h_ != -1 && h_ != h)
							append(eh, eo_, h, h_), fo_[h_]++;
						i = pp[i];
					} else {
						h_ = hhi[j];
						if (h_ != -1 && h_ != h)
							append(eh, eo_, h_, h), fo_[h]++;
						h_ = hhj[j];
						if (h_ != -1 && h_ != h)
							append(eh, eo_, h, h_), fo_[h_]++;
						j = pp[j];
					}
				if (hhi[i] != -1)
					append(eh, eo_, hhi[i], h);
				if (hhj[i] != -1)
					append(eh, eo_, hhj[i], h);
			}
			for (h = 0; h < m; h++)
				dfs2(h);
			yes = 1;
			for (h = 0; h < m; h++)
				if (fo_[h] > 0) {
					yes = 0;
					break;
				}
			printf(yes ? "Yes\n" : "No\n");
			for (h = 0; h < m; h++)
				free(eh[h]);
		}
		for (i = 0; i < n; i++)
			free(ej[i]);
	}
	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:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
jail.c:52:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &n);
      |   ^~~~~~~~~~~~~~~
jail.c:57:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~
jail.c:64:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |    scanf("%d", &m);
      |    ^~~~~~~~~~~~~~~
jail.c:67:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d%d", &i, &j), i--, j--;
      |     ^~~~~~~~~~~~~~~~~~~~~
jail.c:81:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |    scanf("%d", &m);
      |    ^~~~~~~~~~~~~~~
jail.c:84:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     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	212 KB	Output is correct
5	Correct	32 ms	304 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	30 ms	1088 KB	Output is correct
10	Correct	44 ms	16128 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	31 ms	304 KB	Output is correct
13	Correct	48 ms	16236 KB	Output is correct
14	Correct	51 ms	16208 KB	Output is correct
15	Correct	47 ms	16196 KB	Output is correct
16	Correct	75 ms	16232 KB	Output is correct
17	Correct	48 ms	16200 KB	Output is correct
18	Correct	60 ms	16196 KB	Output is correct
19	Correct	48 ms	16212 KB	Output is correct
20	Correct	48 ms	16236 KB	Output is correct
21	Correct	48 ms	16240 KB	Output is correct
22	Correct	51 ms	16208 KB	Output is correct

Subtask #2

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	212 KB	Output is correct
4	Incorrect	1 ms	260 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

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	212 KB	Output is correct
4	Incorrect	1 ms	260 KB	Output isn't correct
5	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	212 KB	Output is correct
4	Incorrect	1 ms	260 KB	Output isn't correct
5	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	212 KB	Output is correct
4	Incorrect	1 ms	260 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	6 ms	212 KB	Output is correct
6	Incorrect	1 ms	340 KB	Output isn't correct
7	Halted	0 ms	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	212 KB	Output is correct
5	Correct	32 ms	304 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	30 ms	1088 KB	Output is correct
10	Correct	44 ms	16128 KB	Output is correct
11	Correct	5 ms	212 KB	Output is correct
12	Correct	31 ms	304 KB	Output is correct
13	Correct	48 ms	16236 KB	Output is correct
14	Correct	51 ms	16208 KB	Output is correct
15	Correct	47 ms	16196 KB	Output is correct
16	Correct	75 ms	16232 KB	Output is correct
17	Correct	48 ms	16200 KB	Output is correct
18	Correct	60 ms	16196 KB	Output is correct
19	Correct	48 ms	16212 KB	Output is correct
20	Correct	48 ms	16236 KB	Output is correct
21	Correct	48 ms	16240 KB	Output is correct
22	Correct	51 ms	16208 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	212 KB	Output is correct
26	Incorrect	1 ms	260 KB	Output isn't correct
27	Halted	0 ms	0 KB	-