oj.uz

Submission #706787

# Submission time Handle Problem Language Result Execution time Memory
706787 2023-03-07T17:39:07 Z rainboy Parking (CEOI22_parking) C
20 / 100
 76 ms 6864 KB 
#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, stuck;

	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;
	stuck = 0;
	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)
				stuck = 1;
			if (c == 0)
				stuck = 0;
			cnt += c, k++;
		}
	if (stuck) {
		printf("-1\n");
		return 0;
	}
	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 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

Subtask #2
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 33 ms 2692 KB Output is partially correct
2 Partially correct 33 ms 3012 KB Output is partially correct
3 Partially correct 31 ms 2516 KB Output is partially correct
4 Partially correct 32 ms 2480 KB Output is partially correct
5 Partially correct 32 ms 3020 KB Output is partially correct

Subtask #3
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Partially correct 0 ms 212 KB Output is partially correct

Subtask #4
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 212 KB Output is partially correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Partially correct 1 ms 212 KB Output is partially correct
8 Correct 1 ms 212 KB Output is correct
9 Partially correct 0 ms 212 KB Output is partially correct
10 Partially correct 53 ms 4224 KB Output is partially correct
11 Correct 43 ms 4236 KB Output is correct
12 Correct 41 ms 4172 KB Output is correct
13 Partially correct 53 ms 4308 KB Output is partially correct
14 Correct 45 ms 4320 KB Output is correct
15 Correct 39 ms 4172 KB Output is correct
16 Partially correct 54 ms 4260 KB Output is partially correct
17 Correct 39 ms 4172 KB Output is correct
18 Partially correct 53 ms 4360 KB Output is partially correct

Subtask #5
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 212 KB Output is partially correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 0 ms 212 KB Output is partially correct
5 Correct 1 ms 212 KB Output is correct
6 Partially correct 1 ms 212 KB Output is partially correct
7 Correct 1 ms 340 KB Output is correct
8 Partially correct 0 ms 340 KB Output is partially correct
9 Partially correct 1 ms 340 KB Output is partially correct
10 Correct 1 ms 340 KB Output is correct
11 Partially correct 0 ms 340 KB Output is partially correct
12 Partially correct 1 ms 340 KB Output is partially correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Partially correct 1 ms 340 KB Output is partially correct
17 Correct 0 ms 212 KB Output is correct
18 Partially correct 0 ms 212 KB Output is partially correct
19 Partially correct 1 ms 300 KB Output is partially correct
20 Partially correct 0 ms 340 KB Output is partially correct
21 Correct 0 ms 340 KB Output is correct
22 Partially correct 0 ms 340 KB Output is partially correct
23 Correct 1 ms 340 KB Output is correct
24 Partially correct 1 ms 340 KB Output is partially correct

Subtask #6
3.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 33 ms 2692 KB Output is partially correct
12 Partially correct 33 ms 3012 KB Output is partially correct
13 Partially correct 31 ms 2516 KB Output is partially correct
14 Partially correct 32 ms 2480 KB Output is partially correct
15 Partially correct 32 ms 3020 KB Output is partially correct
16 Partially correct 0 ms 212 KB Output is partially correct
17 Correct 1 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 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Partially correct 1 ms 212 KB Output is partially correct
23 Correct 1 ms 212 KB Output is correct
24 Partially correct 0 ms 212 KB Output is partially correct
25 Partially correct 53 ms 4224 KB Output is partially correct
26 Correct 43 ms 4236 KB Output is correct
27 Correct 41 ms 4172 KB Output is correct
28 Partially correct 53 ms 4308 KB Output is partially correct
29 Correct 45 ms 4320 KB Output is correct
30 Correct 39 ms 4172 KB Output is correct
31 Partially correct 54 ms 4260 KB Output is partially correct
32 Correct 39 ms 4172 KB Output is correct
33 Partially correct 53 ms 4360 KB Output is partially correct
34 Partially correct 1 ms 212 KB Output is partially correct
35 Correct 1 ms 212 KB Output is correct
36 Partially correct 0 ms 212 KB Output is partially correct
37 Partially correct 0 ms 212 KB Output is partially correct
38 Correct 1 ms 212 KB Output is correct
39 Partially correct 1 ms 212 KB Output is partially correct
40 Correct 1 ms 340 KB Output is correct
41 Partially correct 0 ms 340 KB Output is partially correct
42 Partially correct 1 ms 340 KB Output is partially correct
43 Correct 1 ms 340 KB Output is correct
44 Partially correct 0 ms 340 KB Output is partially correct
45 Partially correct 1 ms 340 KB Output is partially correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Partially correct 1 ms 340 KB Output is partially correct
50 Correct 0 ms 212 KB Output is correct
51 Partially correct 0 ms 212 KB Output is partially correct
52 Partially correct 1 ms 300 KB Output is partially correct
53 Partially correct 0 ms 340 KB Output is partially correct
54 Correct 0 ms 340 KB Output is correct
55 Partially correct 0 ms 340 KB Output is partially correct
56 Correct 1 ms 340 KB Output is correct
57 Partially correct 1 ms 340 KB Output is partially correct
58 Partially correct 52 ms 6268 KB Output is partially correct
59 Partially correct 52 ms 6700 KB Output is partially correct
60 Partially correct 47 ms 5856 KB Output is partially correct
61 Partially correct 53 ms 6256 KB Output is partially correct
62 Correct 44 ms 6860 KB Output is correct
63 Partially correct 53 ms 6572 KB Output is partially correct
64 Correct 54 ms 6828 KB Output is correct
65 Partially correct 54 ms 6500 KB Output is partially correct
66 Partially correct 53 ms 6732 KB Output is partially correct
67 Correct 43 ms 6572 KB Output is correct
68 Partially correct 52 ms 6832 KB Output is partially correct
69 Partially correct 64 ms 6564 KB Output is partially correct
70 Correct 47 ms 6620 KB Output is correct
71 Correct 43 ms 6724 KB Output is correct
72 Correct 44 ms 6684 KB Output is correct
73 Partially correct 57 ms 6864 KB Output is partially correct
74 Correct 43 ms 6576 KB Output is correct
75 Partially correct 60 ms 6576 KB Output is partially correct
76 Partially correct 76 ms 6772 KB Output is partially correct
77 Partially correct 56 ms 6636 KB Output is partially correct
78 Correct 56 ms 6696 KB Output is correct
79 Partially correct 62 ms 6544 KB Output is partially correct
80 Correct 49 ms 6608 KB Output is correct
81 Partially correct 54 ms 6708 KB Output is partially correct