Submission #829578

#	Time	Username	Problem	Language	Result	Execution time	Memory
829578		rainboy	Airplane (NOI23_airplane)	C11	63 / 100	1067 ms	15032 KiB

Main

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

#define N	200000
#define M	400000
#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 aa[N], n;

int *ej[N], eo[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;
}

int dd[N];

int solve(int t) {
	static char visited[N];
	int i, i_, o;

	for (i = 0; i < n; i++)
		dd[i] = INF;
	dd[0] = 0;
	memset(visited, 0, n * sizeof *visited);
	while (1) {
		i_ = -1;
		for (i = 0; i < n; i++)
			if (!visited[i] && dd[i] != INF && (i_ == -1 || dd[i_] > dd[i]))
				i_ = i;
		i = i_;
		if (i == -1)
			return 0;
		if (i == n - 1)
			return 1;
		visited[i] = 1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o], d = max(dd[i] + 1, aa[j]);

			if (d + aa[j] <= t)
				dd[j] = min(dd[j], d);
		}
	}
}

int main() {
	int m, h, i, j, subtask, lower, upper;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	subtask = 1;
	for (h = 0; h < m; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
		if (i != h || j != h + 1)
			subtask = 3;
	}
	if (subtask == 1) {
		int x, y;

		x = 0;
		for (i = 0; i < n; i++)
			x = max(x, aa[i] - i);
		y = 0;
		for (i = 0; i < n; i++)
			y = max(y, aa[i] - (n - 1 - i));
		printf("%d\n", n - 1 + x + y);
	} else {
		lower = -1, upper = INF;
		while (upper - lower > 1) {
			int t = (lower + upper) / 2;

			if (solve(t))
				upper = t;
			else
				lower = t;
		}
		printf("%d\n", upper);
	}
	return 0;
}

Compilation message (stderr)

Main.c: In function 'append':
Main.c:19:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   19 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:57:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:59:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
Main.c:64:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 31 / 31
• Subtask 4: 0 / 37