Submission #706780

#	Time	Username	Problem	Language	Result	Execution time	Memory
706780		rainboy	Parking (CEOI22_parking)	C11	0 / 100	36 ms	2928 KiB

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 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_ = INF;
	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_ = INF;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++)
			bb[j] = aa[(i + j) % n];
		k_ = min(k_, solve1(bb, n) + 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) {
			if (i != j) {
				ij[h << 1 | 0] = i, ij[h << 1 | 1] = j;
				eh[i][eo[i]++] = h << 1 | 0, eh[j][eo[j]++] = h << 1 | 1;
			} else
				d--;
		}
	}
	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 (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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 15
• Subtask 5: 0 / 25
• Subtask 6: 0 / 15