Submission #1251211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251211		kaiboy	Toll (BOI17_toll)	C++20	100 / 100	55 ms	9544 KiB

toll

#include <algorithm>
#include <iostream>

using namespace std;

const int  N_ = 1 << 16;
const int   K = 5;
const int INF = 0x3f3f3f3f;

int **st[N_ << 1], n_;
int k;

int **new_dd(bool zeroes) {
	int **dd = new int *[k];
	for (int a = 0; a < k; a++) {
		dd[a] = new int[k];
		fill_n(dd[a], k, INF);
		if (zeroes)
			dd[a][a] = 0;
	}
	return dd;
}

void delete_dd(int **dd) {
	for (int a = 0; a < k; a++)
		delete[] dd[a];
	delete[] dd;
}

int **merge(int **dd, int **ee) {
	int **ff = new_dd(false);
	for (int a = 0; a < k; a++)
		for (int b = 0; b < k; b++)
			for (int c = 0; c < k; c++)
				ff[a][b] = min(ff[a][b], dd[a][c] + ee[c][b]);
	return ff;
}

int **query(int l, int r) {
	int **pp = new_dd(true), **qq = new_dd(true);
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if (l & 1) {
			int **dd = merge(pp, st[l++]);
			delete_dd(pp), pp = dd;
		}
		if (!(r & 1)) {
			int **dd = merge(st[r--], qq);
			delete_dd(qq), qq = dd;
		}
	}
	int **dd = merge(pp, qq);
	delete_dd(pp), delete_dd(qq);
	return dd;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, m, q; cin >> k >> n >> m >> q;
	n = (n - 1) / k;
	for (n_ = 1; n_ < n; n_ <<= 1)
		;
	for (int i = 0; i < n_; i++)
		st[i + n_] = new_dd(false);
	while (m--) {
		int i, j, w; cin >> i >> j >> w;
		st[i / k + n_][i % k][j % k] = w;
	}
	for (int i = n_ - 1; i; i--) {
		int l = i << 1, r = l ^ 1;
		st[i] = merge(st[l], st[r]);
	}
	while (q--) {
		int i, j; cin >> i >> j;
		int l = i / k, a = i % k;
		int r = j / k, b = j % k;
		if (l == r) {
			cout << "-1\n";
			continue;
		}
		r--;
		int **dd = query(l, r), d = dd[a][b];
		if (d == INF)
			d = -1;
		cout << d << '\n';
		delete_dd(dd);
	}
	return 0;
}

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