oj.uz

Submission #706786

# Submission time Handle Problem Language Result Execution time Memory
706786 2023-03-07T17:38:09 Z rainboy Parking (CEOI22_parking) C
4 / 100
 43 ms 3024 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 = k == 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 (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 31 ms 2732 KB Output is partially correct
2 Partially correct 33 ms 2940 KB Output is partially correct
3 Partially correct 43 ms 2508 KB Output is partially correct
4 Partially correct 31 ms 2384 KB Output is partially correct
5 Partially correct 32 ms 3024 KB Output is partially correct

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 15.0

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

Subtask #5
0.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 Partially correct 0 ms 212 KB Output is partially correct
4 Partially correct 0 ms 212 KB Output is partially correct
5 Incorrect 1 ms 300 KB Output isn't correct
6 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 31 ms 2732 KB Output is partially correct
12 Partially correct 33 ms 2940 KB Output is partially correct
13 Partially correct 43 ms 2508 KB Output is partially correct
14 Partially correct 31 ms 2384 KB Output is partially correct
15 Partially correct 32 ms 3024 KB Output is partially correct
16 Partially correct 0 ms 212 KB Output is partially correct
17 Incorrect 0 ms 212 KB Output isn't correct
18 Halted 0 ms 0 KB -