Submission #544737

#	Time	Username	Problem	Language	Result	Execution time	Memory
544737		rainboy	Love Polygon (BOI18_polygon)	C11	100 / 100	104 ms	19888 KiB

polygon

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

char ss[N * 2][16];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = strcmp(ss[hh[j]], ss[h]);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int *ej[N], eo[N], dp[N], dq[N]; char visited[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void dfs(int i) {
	int o, x, y;

	visited[i] = 1;
	x = 0, y = 0;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		if (!visited[j]) {
			dfs(j);
			x += dq[j];
			if (dp[j] == dq[j])
				y = 1;
		}
	}
	dp[i] = x, dq[i] = x + y;
}

int main() {
	static int ii[N * 2], hh[N * 2], pp[N];
	int n, h, i, j, ans;

	scanf("%d", &n);
	if (n % 2 != 0) {
		printf("-1\n");
		return 0;
	}
	for (h = 0; h < n * 2; h++) {
		scanf("%s", ss[h]);
		hh[h] = h;
	}
	sort(hh, 0, n * 2);
	for (h = 0, i = 0; h < n * 2; h++)
		ii[hh[h]] = h + 1 == n * 2 || strcmp(ss[hh[h + 1]], ss[hh[h]]) ? i++ : i;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n; h++) {
		i = ii[h * 2 + 0], j = ii[h * 2 + 1];
		pp[i] = j;
		append(j, i);
	}
	ans = n;
	for (i = 0; i < n; i++)
		if (!visited[i]) {
			int j_;

			for (j = i; !visited[j]; j = pp[j])
				visited[j] = 1;
			j_ = j;
			for (j = i; j != j_; j = pp[j])
				visited[j] = 0;
			j = j_;
			do
				dfs(j), j = pp[j];
			while (j != j_);
			if (j == pp[j])
				ans -= dq[j];
			else if (j == pp[pp[j]])
				ans -= dp[j] + dp[pp[j]] + 2;
			else {
				int i_, x, y, z, tmp;

				i_ = -1, x = -1, y = 0;
				do {
					tmp = max(x == -1 ? -1 : x + dp[i_] + dp[j] + 1, y + dq[j]), x = y, y = tmp;
					i_ = j, j = pp[j];
				} while (j != j_);
				z = y;
				i_ = j_, j = pp[j_], x = -1, y = 0;
				do {
					tmp = max(x == -1 ? -1 : x + dp[i_] + dp[j] + 1, y + dq[j]), x = y, y = tmp;
					i_ = j, j = pp[j];
				} while (j != j_);
				z = max(z, x + dp[i_] + dp[j] + 1);
				ans -= z;
			}
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

polygon.c: In function 'append':
polygon.c:45:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   45 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
polygon.c: In function 'main':
polygon.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
polygon.c:78:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%s", ss[h]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25