Submission #683602

#	Time	Username	Problem	Language	Result	Execution time	Memory
683602		rainboy	Railway Trip (JOI17_railway_trip)	C11	0 / 100	553 ms	10248 KiB

railway_trip

#include <stdio.h>
#include <stdlib.h>
 
#define N	100000
#define INF	0x3f3f3f3f
 
int min(int a, int b) { return a < b ? a : b; }
 
int aa[N], ll[N], ll_[N], ddl[N], rr[N], rr_[N], ddr[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 bfs(int n, int s, int t) {
	static int qu[N], dd[N];
	int cnt, h, i, j, d, o;
 
	for (i = 0; i < n; i++)
		dd[i] = n;
	cnt = 0;
	dd[s] = 0, qu[cnt++] = s;
	for (h = 0; h < cnt; h++) {
		i = qu[h], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (dd[j] > d)
				dd[j] = d, qu[cnt++] = j;
		}
	}
	return dd[t];
}
 
int solve(int i, int j, int d, int x) {
	int d_, tmp;
 
	if (i > j)
		tmp = i, i = j, j = tmp;
	if (i == -1 || j == n)
		return INF;
	if (i == j)
		return d + x;
	d_ = INF;
	if (rr_[i] >= j && ll_[j] <= i) {
		d_ = d + x;
		if (aa[i] < aa[j])
			d_ += ddr[i];
		else if (aa[i] > aa[j])
			d_ += ddl[j];
		else
			d_ += ddl[j] - ddl[i];
	}
	if (x < 4) {
		d_ = min(d_, solve(ll[i], j, d, x + 1));
		d_ = min(d_, solve(rr[i], j, d, x + 1));
		d_ = min(d_, solve(i, ll[j], d, x + 1));
		d_ = min(d_, solve(i, rr[j], d, x + 1));
	}
	return d_;
}
 
int main() {
	static int qu[N];
	int k, q, i, j, cnt;
 
	scanf("%d%d%d", &n, &k, &q);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	cnt = 0;
	for (i = 0; i < n; i++) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		ll[i] = cnt == 0 ? -1 : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (i = 0; i < n; i++)
		if (ll[i] == -1)
			ll_[i] = -1, ddl[i] = 0;
		else if (aa[i] != aa[ll[i]])
			ll_[i] = ll[i], ddl[i] = 1;
		else
			ll_[i] = ll_[ll[i]], ddl[i] = ddl[ll[i]] + 1;
	cnt = 0;
	for (i = n - 1; i >= 0; i--) {
		while (cnt && aa[qu[cnt - 1]] < aa[i])
			cnt--;
		rr[i] = cnt == 0 ? n : qu[cnt - 1];
		qu[cnt++] = i;
	}
	for (i = n - 1; i >= 0; i--)
		if (rr[i] == n)
			rr_[i] = n, ddr[i] = 0;
		else if (aa[i] != aa[rr[i]])
			rr_[i] = rr[i], ddr[i] = 1;
		else
			rr_[i] = rr_[rr[i]], ddr[i] = ddr[rr[i]] + 1;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 0; i < n; i++)
		if (ll[i] != -1)
			append(i, ll[i]), append(ll[i], i);
	for (i = 0; i < n; i++)
		if (rr[i] != n)
			append(i, rr[i]), append(rr[i], i);
	while (q--) {
		int s, t, u, v, d, d_;
		int tmp;
 
		scanf("%d%d", &i, &j), i--, j--;
		if (i > j)
			tmp = i, i = j, j = tmp;
		if (rr[i] >= j && ll[j] <= i) {
			d_ = 0;
			goto print;
		}
		d = 0;
		u = i, s = 0;
		while ((s == 0 ? rr_[u] <= j : (rr_[ll_[u]] <= j && rr_[rr_[u]] <= j)))
			if (s == 0) {
				if (ddl[u] < ddr[u])
					d += ddl[u], u = ll_[u], s = 0;
				else if (ddl[u] > ddr[u])
					d += ddr[u], u = rr_[u], s = 0;
				else
					d += ddl[u], s = 1;
			} else {
				if (aa[ll_[u]] > aa[rr_[u]])
					u = ll_[u], s = 0;
				else if (aa[ll_[u]] < aa[rr_[u]])
					u = rr_[u], s = 0;
				else {
					if (ddl[ll_[u]] < ddr[rr_[u]])
						d += ddl[ll_[u]], u = ll_[ll_[u]], s = 0;
					else if (ddl[ll_[u]] > ddr[rr_[u]])
						d += ddr[rr_[u]], u = rr_[rr_[u]], s = 0;
					else
						d += ddl[ll_[u]], u = ll_[u], s = 1;
				}
			}
		v = j, t = 0;
		while ((t == 0 ? ll_[v] >= i : (ll_[ll_[v]] >= i && ll_[rr_[v]] >= i)))
			if (t == 0) {
				if (ddl[v] < ddr[v])
					d += ddl[v], v = ll_[v], t = 0;
				else if (ddl[v] > ddr[v])
					d += ddr[v], v = rr_[v], t = 0;
				else
					d += ddl[v], t = 1;
			} else {
				if (aa[ll_[v]] > aa[rr_[v]])
					v = ll_[v], t = 0;
				else if (aa[ll_[v]] < aa[rr_[v]])
					v = rr_[v], t = 0;
				else {
					if (ddl[ll_[v]] < ddr[rr_[v]])
						d += ddl[ll_[v]], v = ll_[ll_[v]], t = 0;
					else if (ddl[ll_[v]] > ddr[rr_[v]])
						d += ddr[rr_[v]], v = rr_[rr_[v]], t = 0;
					else
						d += ddl[ll_[v]], v = ll_[v], t = 1;
				}
			}
		d_ = INF;
		if (s == 0 && t == 0) {
			d_ = min(d_, solve(u, v, d, 0) - 1);
		} else if (s == 0 && t == 1) {
			d_ = min(d_, solve(u, ll_[v], d, 0) - 1);
			d_ = min(d_, solve(u, rr_[v], d, 0) - 1);
		} else if (s == 1 && t == 0) {
			d_ = min(d_, solve(ll_[u], v, d, 0) - 1);
			d_ = min(d_, solve(rr_[u], v, d, 0) - 1);
		} else {
			d_ = min(d_, solve(ll_[u], ll_[v], d, 0) - 1);
			d_ = min(d_, solve(ll_[u], rr_[v], d, 0) - 1);
			d_ = min(d_, solve(rr_[u], ll_[v], d, 0) - 1);
			d_ = min(d_, solve(rr_[u], rr_[v], d, 0) - 1);
		}
print:
		printf("%d\n", d_);
	}
	return 0;
}

Compilation message (stderr)

railway_trip.c: In function 'main':
railway_trip.c:72:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.c:74:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
railway_trip.c:115:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55