Submission #544732

#	Time	Username	Problem	Language	Result	Execution time	Memory
544732		rainboy	Toll (BOI17_toll)	C11	100 / 100	85 ms	15924 KiB

toll

#include <stdio.h>

#define N	50000
#define K	5
#define Q	10000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int dd[N][K][K], ii[Q], jj[Q], ans[Q], k;

void solve(int *hh, int l, int r, int q) {
	static int dd1[N][K][K], dd2[N][K][K];
	int m, h, hl, hm, hr, i, j, a, b, c, tmp;

	if (q == 0)
		return;
	m = (l + r) / 2;
	hl = 0, hm = 0, hr = q;
	while (hm < hr)
		if (ii[hh[hm]] / k <= m && m <= jj[hh[hm]] / k)
			hm++;
		else if (jj[hh[hm]] / k < m) {
			tmp = hh[hl], hh[hl] = hh[hm], hh[hm] = tmp;
			hl++, hm++;
		} else {
			hr--;
			tmp = hh[hm], hh[hm] = hh[hr], hh[hr] = tmp;
		}
	for (i = l; i <= m; i++)
		for (a = 0; a < k; a++)
			for (b = 0; b < k; b++)
				dd1[i][a][b] = INF;
	for (i = m; i <= r; i++)
		for (a = 0; a < k; a++)
			for (b = 0; b < k; b++)
				dd2[i][a][b] = INF;
	for (a = 0; a < k; a++)
		dd1[m][a][a] = dd2[m][a][a] = 0;
	for (i = m; i > l; i--)
		for (a = 0; a < k; a++)
			for (b = 0; b < k; b++) {
				int x = dd1[i][a][b];

				if (x != INF)
					for (c = 0; c < k; c++)
						dd1[i - 1][c][b] = min(dd1[i - 1][c][b], dd[i - 1][c][a] + x);
			}
	for (i = m; i < r; i++)
		for (a = 0; a < k; a++)
			for (b = 0; b < k; b++) {
				int x = dd2[i][a][b];

				if (x != INF)
					for (c = 0; c < k; c++)
						dd2[i + 1][a][c] = min(dd2[i + 1][a][c], x + dd[i][b][c]);
			}
	for (h = hl; h < hr; h++) {
		int h_ = hh[h], x;

		i = ii[h_] / k, a = ii[h_] % k, j = jj[h_] / k, b = jj[h_] % k;
		x = INF;
		for (c = 0; c < k; c++)
			x = min(x, dd1[i][a][c] + dd2[j][c][b]);
		ans[h_] = x;
	}
	solve(hh, l, m - 1, hl);
	solve(hh + hr, m + 1, r, q - hr);
}

int main() {
	static int hh[Q];
	int n, m, q, h, i, j, a, b;

	scanf("%d%d%d%d", &k, &n, &m, &q), n = (n + k - 1) / k;
	for (i = 0; i + 1 < n; i++)
		for (a = 0; a < k; a++)
			for (b = 0; b < k; b++)
				dd[i][a][b] = INF;
	while (m--) {
		int d;

		scanf("%d%d%d", &i, &j, &d);
		dd[i / k][i % k][j % k] = d;
	}
	for (h = 0; h < q; h++) {
		scanf("%d%d", &ii[h], &jj[h]);
		hh[h] = h;
	}
	solve(hh, 0, n - 1, q);
	for (h = 0; h < q; h++)
		printf("%d\n", ans[h] == INF ? -1 : ans[h]);
	return 0;
}

Compilation message (stderr)

toll.c: In function 'main':
toll.c:75:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |  scanf("%d%d%d%d", &k, &n, &m, &q), n = (n + k - 1) / k;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:83:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%d%d%d", &i, &j, &d);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.c:87:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   scanf("%d%d", &ii[h], &jj[h]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44