Submission #661138

#	Time	Username	Problem	Language	Result	Execution time	Memory
661138		rainboy	IOI Fever (JOI21_fever)	C11	37 / 100	5050 ms	4632 KiB

fever

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

#define N	100000
#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 xx[N], yy[N], uu[N], vv[N], tt[N], n;

/*
 *      2     
 *      ^     
 *      |     
 * 3 <- o -> 1
 *      |     
 *      v     
 *      4     
 */

int solve() {
	static int dd[N];
	static char visited[N];
	int i, j, k, d, d_;

	for (i = 0; i < n; i++)
		uu[i] = xx[i] - yy[i], vv[i] = xx[i] + yy[i];
	for (i = 0; i < n; i++)
		if (uu[i] <= 0 && vv[i] <= 0)
			tt[i] = 1;
		else if (uu[i] > 0 && vv[i] <= 0)
			tt[i] = 2;
		else if (uu[i] > 0 && vv[i] > 0)
			tt[i] = 3;
		else
			tt[i] = 4;
	memset(visited, 0, n * sizeof *visited);
	memset(dd, 0x3f, n * sizeof *dd), dd[0] = 0;
	k = 0;
	while (1) {
		i = -1;
		for (j = 0; j < n; j++)
			if (!visited[j] && dd[j] != INF)
				if (i == -1 || dd[i] > dd[j])
					i = j;
		if (i == -1)
			break;
		visited[i] = 1;
		d = dd[i];
		k++;
		if (tt[i] == 1) {
			for (j = 0; j < n; j++)
				if (uu[i] == uu[j] && d <= (d_ = vv[j] - vv[i])
						|| yy[i] == yy[j] && d <= (d_ = xx[j] - xx[i])
						|| vv[i] == vv[j] && d <= (d_ = uu[j] - uu[i]))
					dd[j] = min(dd[j], d_);
		} else if (tt[i] == 2) {
			for (j = 0; j < n; j++)
				if (vv[i] == vv[j] && d <= (d_ = uu[i] - uu[j])
						|| xx[i] == xx[j] && d <= (d_ = yy[j] - yy[i])
						|| uu[i] == uu[j] && d <= (d_ = vv[j] - vv[i]))
					dd[j] = min(dd[j], d_);
		} else if (tt[i] == 3) {
			for (j = 0; j < n; j++)
				if (uu[i] == uu[j] && d <= (d_ = vv[i] - vv[j])
						|| yy[i] == yy[j] && d <= (d_ = xx[i] - xx[j])
						|| vv[i] == vv[j] && d <= (d_ = uu[i] - uu[j]))
					dd[j] = min(dd[j], d_);
		} else {
			for (j = 0; j < n; j++)
				if (vv[i] == vv[j] && d <= (d_ = uu[j] - uu[i])
						|| xx[i] == xx[j] && d <= (d_ = yy[i] - yy[j])
						|| uu[i] == uu[j] && d <= (d_ = vv[i] - vv[j]))
					dd[j] = min(dd[j], d_);
		}
	}
	return k;
}

int main() {
	int h, i, k_, tmp;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d%d", &xx[i], &yy[i]);
	for (i = 1; i < n; i++)
		xx[i] -= xx[0], yy[i] -= yy[0];
	xx[0] = 0, yy[0] = 0;
	k_ = 0;
	for (h = 0; h < 4; h++) {
		k_ = max(k_, solve());
		for (i = 0; i < n; i++)
			tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
	}
	printf("%d\n", k_);
	return 0;
}

Compilation message (stderr)

fever.c: In function 'solve':
fever.c:54:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   54 |     if (uu[i] == uu[j] && d <= (d_ = vv[j] - vv[i])
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:56:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   56 |       || vv[i] == vv[j] && d <= (d_ = uu[j] - uu[i]))
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:60:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |     if (vv[i] == vv[j] && d <= (d_ = uu[i] - uu[j])
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:62:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |       || uu[i] == uu[j] && d <= (d_ = vv[j] - vv[i]))
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:66:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |     if (uu[i] == uu[j] && d <= (d_ = vv[i] - vv[j])
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:68:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   68 |       || vv[i] == vv[j] && d <= (d_ = uu[i] - uu[j]))
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:72:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   72 |     if (vv[i] == vv[j] && d <= (d_ = uu[j] - uu[i])
      |         ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c:74:25: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   74 |       || uu[i] == uu[j] && d <= (d_ = vv[i] - vv[j]))
      |          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fever.c: In function 'main':
fever.c:84:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
fever.c:86:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   scanf("%d%d", &xx[i], &yy[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31