Submission #706784

# Submission time Handle Problem Language Result Execution time Memory
706784 2023-03-07T17:33:55 Z rainboy Parking (CEOI22_parking) C
10 / 100
84 ms 6860 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, 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) {
	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:45:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:48:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
# 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 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
# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 2720 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 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 0 ms 340 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 1 ms 340 KB Output is correct
9 Partially correct 1 ms 300 KB Output is partially correct
# 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 0 ms 340 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 1 ms 340 KB Output is correct
9 Partially correct 1 ms 300 KB Output is partially correct
10 Partially correct 56 ms 6796 KB Output is partially correct
11 Correct 45 ms 6640 KB Output is correct
12 Correct 44 ms 6604 KB Output is correct
13 Partially correct 84 ms 6748 KB Output is partially correct
14 Correct 43 ms 6860 KB Output is correct
15 Correct 43 ms 6620 KB Output is correct
16 Partially correct 56 ms 6860 KB Output is partially correct
17 Correct 41 ms 6604 KB Output is correct
18 Partially correct 55 ms 6752 KB Output is partially correct
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 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 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 Incorrect 35 ms 2720 KB Output isn't correct
12 Halted 0 ms 0 KB -