oj.uz

Submission #706783

# Submission time Handle Problem Language Result Execution time Memory
706783 2023-03-07T17:21:29 Z rainboy Parking (CEOI22_parking) C
2 / 100
 33 ms 2768 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 ij[M * 2], eh[N][2], eo[N];

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

	k = 0;
	for (i = 0; i < n; i++)
		if (aa[i] == 1)
			k++;
	k_ = n;
	for (i = 0; i < n; i++) {
		if (aa[i] == 1)
			k--;
		k_ = min(k_, k);
		if (aa[i] == 0)
			k++;
	}
	return k_;
}

int solve2(int *aa, int n) {
	static int bb[N];
	int i, j, k_;

	k_ = n;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			bb[j] = aa[(i + j) % n];
		k_ = min(k_, solve1(bb + 1, n - 1) + 1);
	}
	return k_;
}

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:47:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:50:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   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 1 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.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 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 340 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.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 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 340 KB Output is correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 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 1 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 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Partially correct 0 ms 212 KB Output is partially correct
11 Incorrect 33 ms 2768 KB Output isn't correct
12 Halted 0 ms 0 KB -