Submission #706785

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706785	2023-03-07T17:35:42 Z	rainboy	Parking (CEOI22_parking)	C	12 / 100	61 ms	4560 KB

Main

#include <stdio.h>

#define N	200000
#define M	200000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int ij[M * 2], eh[N][2], eo[N];

int solve1(int *aa, int n) {
	int i, k;

	i = 0, k = 0;
	while (i < n) {
		while (i < n && aa[i] == 1)
			i++;
		while (i < n && aa[i] == 0)
			i++;
		k++;
	}
	return k - 1;
}

int solve2(int *aa, int n) {
	int i, k;

	k = 0;
	for (i = 0; i < n; i++)
		if (aa[i] != aa[(i + 1) % n])
			k++;
	return max(k / 2, 1);
}

int main() {
	static char visited[N];
	static int aa[N];
	int n, m, h, h_, i, i_, j, k, c, d, cnt, o;

	scanf("%d%d", &n, &m);
	k = 0, d = n;
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		if (i == -1)
			k++;
		else if (j != -1) {
			ij[h << 1 | 0] = i, ij[h << 1 | 1] = j;
			eh[i][eo[i]++] = h << 1 | 0, eh[j][eo[j]++] = h << 1 | 1;
			if (i == j)
				d--;
		}
	}
	for (i = 0; i < n; i++)
		if (eo[i] == 0)
			k++;
	cnt = d;
	for (i = 0; i < n; i++)
		if (eo[i] == 1 && !visited[i]) {
			h_ = -1, i_ = i, m = 0;
			do {
				visited[i_] = 1;
				for (o = eo[i_]; o--; ) {
					h = eh[i_][o], j = ij[h ^ 1];
					if (h != (h_ ^ 1)) {
						aa[m++] = h & 1;
						h_ = h, i_ = j;
						break;
					}
				}
			} while (eo[i_] != 1);
			visited[i_] = 1;
			c = solve1(aa, m);
			if (k == 0 && c > 0) {
				printf("-1\n");
				return 0;
			}
			cnt += c, k++;
		}
	for (i = 0; i < n; i++)
		if (eo[i] == 2 && !visited[i]) {
			h_ = -1, i_ = i, m = 0;
			do {
				visited[i_] = 1;
				for (o = eo[i_]; o--; ) {
					h = eh[i_][o], j = ij[h ^ 1];
					if (h != (h_ ^ 1)) {
						aa[m++] = h & 1;
						h_ = h, i_ = j;
						break;
					}
				}
			} while (i_ != i);
			if (m == 1)
				continue;
			if (k == 0) {
				printf("-1\n");
				return 0;
			}
			c = solve2(aa, m);
			if (k == 1 && c > 1) {
				printf("-1\n");
				return 0;
			}
			cnt += c;
		}
	printf("%d\n", cnt);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:41:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:44:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 10.0

#	Verdict	Memory	Grader output
1	Partially correct	212 KB	Output is partially correct
2	Partially correct	212 KB	Output is partially correct
3	Partially correct	212 KB	Output is partially correct
4	Partially correct	212 KB	Output is partially correct
5	Partially correct	212 KB	Output is partially correct
6	Correct	212 KB	Output is correct
7	Partially correct	212 KB	Output is partially correct
8	Correct	212 KB	Output is correct
9	Correct	212 KB	Output is correct
10	Partially correct	212 KB	Output is partially correct

Subtask #2
2.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	29 ms	2736 KB	Output is partially correct
2	Partially correct	33 ms	4560 KB	Output is partially correct
3	Partially correct	33 ms	3652 KB	Output is partially correct
4	Partially correct	32 ms	3584 KB	Output is partially correct
5	Partially correct	34 ms	4556 KB	Output is partially correct

Subtask #3
5.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	212 KB	Output is partially correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Partially correct	1 ms	212 KB	Output is partially correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Partially correct	1 ms	212 KB	Output is partially correct
8	Correct	0 ms	212 KB	Output is correct
9	Partially correct	1 ms	340 KB	Output is partially correct

Subtask #4
3.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	212 KB	Output is partially correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Partially correct	1 ms	212 KB	Output is partially correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Partially correct	1 ms	212 KB	Output is partially correct
8	Correct	0 ms	212 KB	Output is correct
9	Partially correct	1 ms	340 KB	Output is partially correct
10	Partially correct	59 ms	4220 KB	Output is partially correct
11	Correct	44 ms	4176 KB	Output is correct
12	Correct	42 ms	4208 KB	Output is correct
13	Partially correct	61 ms	4408 KB	Output is partially correct
14	Correct	44 ms	4388 KB	Output is correct
15	Correct	43 ms	4180 KB	Output is correct
16	Partially correct	57 ms	4428 KB	Output is partially correct
17	Correct	40 ms	4172 KB	Output is correct
18	Partially correct	53 ms	4360 KB	Output is partially correct

Subtask #5
0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	340 KB	Output is partially correct
2	Correct	0 ms	340 KB	Output is correct
3	Partially correct	1 ms	212 KB	Output is partially correct
4	Incorrect	0 ms	212 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	0 ms	212 KB	Output is partially correct
2	Partially correct	0 ms	212 KB	Output is partially correct
3	Partially correct	0 ms	212 KB	Output is partially correct
4	Partially correct	0 ms	212 KB	Output is partially correct
5	Partially correct	0 ms	212 KB	Output is partially correct
6	Correct	0 ms	212 KB	Output is correct
7	Partially correct	0 ms	212 KB	Output is partially correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Partially correct	0 ms	212 KB	Output is partially correct
11	Partially correct	29 ms	2736 KB	Output is partially correct
12	Partially correct	33 ms	4560 KB	Output is partially correct
13	Partially correct	33 ms	3652 KB	Output is partially correct
14	Partially correct	32 ms	3584 KB	Output is partially correct
15	Partially correct	34 ms	4556 KB	Output is partially correct
16	Partially correct	1 ms	212 KB	Output is partially correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	1 ms	212 KB	Output is correct
19	Partially correct	1 ms	212 KB	Output is partially correct
20	Correct	0 ms	212 KB	Output is correct
21	Correct	0 ms	212 KB	Output is correct
22	Partially correct	1 ms	212 KB	Output is partially correct
23	Correct	0 ms	212 KB	Output is correct
24	Partially correct	1 ms	340 KB	Output is partially correct
25	Partially correct	59 ms	4220 KB	Output is partially correct
26	Correct	44 ms	4176 KB	Output is correct
27	Correct	42 ms	4208 KB	Output is correct
28	Partially correct	61 ms	4408 KB	Output is partially correct
29	Correct	44 ms	4388 KB	Output is correct
30	Correct	43 ms	4180 KB	Output is correct
31	Partially correct	57 ms	4428 KB	Output is partially correct
32	Correct	40 ms	4172 KB	Output is correct
33	Partially correct	53 ms	4360 KB	Output is partially correct
34	Partially correct	0 ms	340 KB	Output is partially correct
35	Correct	0 ms	340 KB	Output is correct
36	Partially correct	1 ms	212 KB	Output is partially correct
37	Incorrect	0 ms	212 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Submission #706785

Compilation message

Subtask #1 2.0 / 10.0

Subtask #2 2.0 / 10.0

Subtask #3 5.0 / 25.0

Subtask #4 3.0 / 15.0

Subtask #5 0.0 / 25.0

Subtask #6 0.0 / 15.0

Subtask #1
2.0 / 10.0

Subtask #2
2.0 / 10.0

Subtask #3
5.0 / 25.0

Subtask #4
3.0 / 15.0

Subtask #5
0.0 / 25.0

Subtask #6
0.0 / 15.0