Submission #705134

#	Time	Username	Problem	Language	Result	Execution time	Memory
705134		dubabuba	Toll (BOI17_toll)	C++14	100 / 100	218 ms	142176 KiB

toll

#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int mxn = 3e5 + 10;
const int LOG = 20;
int ans[6][6], tmp[6][6];
int dp[mxn][LOG][6][6];
int k, n, m, q;

void ono_min(int &s, int t) {
	if(s > t) s = t;
}

int box(int u) {
	return u / k;
}

void build() {
	for(int i = 1; i <= LOG; i++) {
		for(int Lbox = 0; Lbox <= box(n - 1); Lbox++) {
			int Mbox = Lbox + (1 << (i - 1));
			int Rbox = Lbox + (1 << i);
			if(Rbox > box(n - 1)) continue;

			for(int l = 0; l < k; l++)
			for(int r = 0; r < k; r++)
			for(int m = 0; m < k; m++)
			ono_min(dp[Lbox][i][l][r], dp[Lbox][i - 1][l][m] + dp[Mbox][i - 1][m][r]);

			// cout << "  > " << Lbox << ' ' << Rbox << '\n';
			// for(int l = 0; l < k; l++)
			// for(int r = 0; r < k; r++) {
			// 	int Lnode = Lbox * k + l;
			// 	int Rnode = Rbox * k + r;
			// 	cout << Lnode << ' ' << Rnode << ": " << dp[Lbox][i][l][r] << '\n';
			// }
		}
	}
}

int main() {
	cin >> k >> n >> m >> q;
	for(int i = 0; i <= box(n - 1); i++)
	for(int j = 0; j < LOG; j++)
	for(int l = 0; l < k; l++)
	for(int r = 0; r < k; r++)
	dp[i][j][l][r] = inf;

	for(int i = 0; i < m; i++) {
		int s, f, t;
		cin >> s >> f >> t;
		dp[box(s)][0][s % k][f % k] = t;
	}

	build();

	while(q--) {
		int Lnode, Rnode;
		cin >> Lnode >> Rnode;

		for(int i = 0; i < k; i++)
		for(int j = 0; j < k; j++)
			ans[i][j] = inf;

		for(int i = 0; i < k; i++)
			ans[i][i] = 0;

		int Lbox = box(Lnode), Rbox = box(Rnode);
		for(int lg = LOG - 1; lg >= 0; lg--) {
			if(Lbox + (1 << lg) <= Rbox) {
				for(int i = 0; i < k; i++)
				for(int j = 0; j < k; j++)
					tmp[i][j] = inf;

				for(int i = 0; i < k; i++)
				for(int j = 0; j < k; j++)
				for(int m = 0; m < k; m++)
					ono_min(tmp[i][j], ans[i][m] + dp[Lbox][lg][m][j]);

				for(int i = 0; i < k; i++)
				for(int j = 0; j < k; j++) {
					// int Lnode = Lbox * k + i;
					// int Rnode = Rbox * k + j;
					// cout << Lnode << ' ' << Rnode << ": " << tmp[i][j] << '\n';
					ans[i][j] = tmp[i][j];
				}
				Lbox += (1 << lg);
			}
		}

		cout << ((ans[Lnode % k][Rnode % k] == inf) ? -1 : ans[Lnode % k][Rnode % k]) << '\n';
	}

	return 0;
}

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