Submission #1111325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111325		sleepntsheep	Airplane (NOI23_airplane)	C11	100 / 100	271 ms	15016 KiB

Main

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

int max(int i, int j) { return i > j ? i : j; }
int min(int i, int j) { return i < j ? i : j; }

#define N 200005

const int oo = 1e9;

int n, m, a[N], *eh[N], eo[N], to, dp[N], dq[N], *focus, t[N * 2], z = oo;

int Lt(int i, int j) { return focus[i] < focus[j]; }
int Min(int i, int j) { return Lt(i, j) ? i : j; }
void pul(int i) { t[i] = Min(t[i * 2], t[i * 2 + 1]); }
void fix(int i) { for (i += n; i /= 2; ) pul(i); }

void pus(int i, int j) {
	int o = eo[i]++;
	if (!o) eh[i] = (int*)malloc(sizeof **eh * 2);
	else if (!(o & (o - 1))) eh[i] = (int*)realloc(eh[i], 2 * o * sizeof **eh);
	eh[i][o] = j;
}

void Dijkstra(int src, int *dp) {
	focus = dp;
	for (int i = 0; i < n; ++i) dp[i] = oo, t[i + n] = i;
	dp[src] = 0;
	dp[n] = oo + 1;
	for (int i = n; --i;) pul(i);
	for (int i = 1; i <= n; ++i) {
		int u = t[1];
		t[u + n] = n;
		fix(u);
		
		for (int v, j = 0; j < eo[u]; ++j) {
			v = eh[u][j];
			int nc = max(dp[u] + 1, a[v]); 
			if (t[v + n] == v && nc < dp[v]) {
				dp[v] = nc;
				fix(v);
			}
		}
	}
}

int main() {
	srand(time(0));
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i) scanf("%d", a + i);
	for (int u, v, i = 0; i < m; ++i)
		scanf("%d%d", &u, &v), pus(--u, --v), pus(v, u);

	Dijkstra(0, dp);
	Dijkstra(n - 1, dq);

	for (int i = 0; i < n; ++i) {
		z = min(z, max(dp[i], dq[i]) * 2);
		for (int k = 0; k < eo[i]; ++k) {
			int j = eh[i][k];
			z = min(z, 2 * max(dp[i], dq[j]) + 1);
		}
	}
	
	printf("%d", z);
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:51:30: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  for (int i = 0; i < n; ++i) scanf("%d", a + i);
      |                              ^~~~~~~~~~~~~~~~~~
Main.c:53:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%d%d", &u, &v), pus(--u, --v), pus(v, u);
      |   ^~~~~~~~~~~~~~~~~~~~~

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