Submission #683594

# Submission time Handle Problem Language Result Execution time Memory
683594 2023-01-18T19:53:30 Z rainboy Railway Trip (JOI17_railway_trip) C
20 / 100
2000 ms 10444 KB
#include <stdio.h>
#include <stdlib.h>

#define N	100000

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 main() {
	static int aa[N], qu[N], ll[N], ll_[N], ddl[N], rr[N], rr_[N], ddr[N];
	int n, 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;
		int tmp;

		scanf("%d%d", &i, &j), i--, j--;
		printf("%d\n", bfs(n, i, j) - 1);
		continue;
		if (i > j)
			tmp = i, i = j, j = tmp;
		if (rr[i] >= j && ll[j] <= i) {
			printf("0\n");
			continue;
		}
		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;
				}
			}
		if (s == 0 && t == 0) {
			if (u == v) {
				d--;
				goto print;
			}
		} else if (s == 0 && t == 1) {
			if (u == ll_[v] || u == rr_[v]) {
				d--;
				goto print;
			}
		} else if (s == 1 && t == 0) {
			if (v == ll_[u] || v == rr_[u]) {
				d--;
				goto print;
			}
		} else {
			if (ll_[u] == ll_[v] || ll_[u] == rr_[v] || rr_[u] == ll_[v] || rr_[u] == rr_[v]) {
				d--;
				goto print;
			}
		}
		if ((s == 0 ? rr[u] <= j : (rr[ll_[u]] <= j && rr[rr_[u]] <= j)) || (t == 0 ? ll[v] >= i : (ll[ll_[v]] >= i && ll[rr_[v]] >= i))) {
			if (s == 1)
				u = rr_[rr_[u]] > j ? rr_[u] : ll_[u];
			if (t == 1)
				v = ll_[ll_[v]] < i ? ll_[v] : rr_[v];
			if (aa[u] < aa[v])
				d += ddr[u];
			else if (aa[u] > aa[v])
				d += ddl[v];
			else
				d += ddl[v] - ddl[u];
			d--;
		}
print:
		printf("%d\n", d);
	}
	return 0;
}

Compilation message

railway_trip.c: In function 'main':
railway_trip.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d%d", &n, &k, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway_trip.c:41:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~
railway_trip.c:82:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 168 ms 9932 KB Output is correct
3 Correct 166 ms 9800 KB Output is correct
4 Correct 158 ms 9816 KB Output is correct
5 Correct 165 ms 9864 KB Output is correct
6 Correct 177 ms 9844 KB Output is correct
7 Correct 159 ms 10068 KB Output is correct
8 Correct 62 ms 8692 KB Output is correct
9 Correct 64 ms 10444 KB Output is correct
10 Correct 67 ms 9660 KB Output is correct
11 Correct 148 ms 10252 KB Output is correct
12 Correct 137 ms 10172 KB Output is correct
13 Correct 135 ms 10204 KB Output is correct
14 Correct 146 ms 10184 KB Output is correct
15 Correct 148 ms 10244 KB Output is correct
16 Correct 135 ms 10204 KB Output is correct
17 Correct 169 ms 10164 KB Output is correct
18 Correct 201 ms 10188 KB Output is correct
19 Correct 76 ms 9308 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 2081 ms 9548 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 9548 KB Time limit exceeded
2 Halted 0 ms 0 KB -