Submission #416468

#	Time	Username	Problem	Language	Result	Execution time	Memory
416468		mbfibat	Toll (BOI17_toll)	C++17	100 / 100	205 ms	89900 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

int n, m, q, k;
int a[50001];
vector<ii> adj[50001], adj_re[50001];
int val[20][50001][5][5];

int comb(int x, int y) {
	return min(x, y); // Replace min with any associative operation
}

void init(int l, int r, int lev) {
	if (l == r) 
		return;

	int mi = (l + r) / 2;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < k; j++)
			val[lev][mi][i][j] = 1e9;
		val[lev][mi][i][i] = 0;
	}
	for (int i = mi - 1; i >= l; i--) {
		for (int j = 0; j < k; j++) {
			for (int z = 0 ; z < k; z++)
				val[lev][i][j][z] = 1e9;
			int u = i * k + j;
			for (ii _ : adj[u]) {
				int v = _.first, c = _.second;
				int nxt = v % k;
				for (int z = 0; z < k; z++)
					val[lev][i][j][z] = comb(val[lev][i][j][z], val[lev][i + 1][nxt][z] + c);
			}
		}
	}
	for (int i = mi + 1; i <= r; i++) {
		for (int j = 0; j < k; j++) {
			for (int z = 0 ; z < k; z++)
				val[lev][i][j][z] = 1e9;
			int u = i * k + j;
			for (ii _ : adj_re[u]) {
				int v = _.first, c = _.second;
				int nxt = v % k;
				for (int z = 0; z < k; z++)
					val[lev][i][j][z] = comb(val[lev][i - 1][nxt][z] + c, val[lev][i][j][z]);
			}
		}
	}
	if (r - l <= 1) return;
	init(l, mi, lev + 1);
	init(mi, r, lev + 1);
}


int main(int argc, char** argv) 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> k >> n >> m >> q;
	for (int i = 0; i < m; i++) {
		int u, v, c; cin >> u >> v >> c;
		adj[u].push_back(ii(v, c));
		adj_re[v].push_back(ii(u, c));
	}
	init(0, (n - 1)/k, 0);

	while (q--) {
		int u, v; cin >> u >> v;
		int id1 = u / k, id2 = v / k;
		if (id1 == id2) cout << -1 << '\n';
		else {
			int lev = 0;
			int l = 0, r = (n - 1)/k;
			while(1) {
				int mi = (l + r) / 2;
				if (id1 <= mi && mi <= id2) break;
				else {
					if (mi < id1) l = mi;
					else r = mi;
					lev++;
				}
			}
			int ans = 1e9;
			for (int i = 0; i < k; i++)
				ans = min(ans, val[lev][id1][u % k][i] + val[lev][id2][v % k][i]);
			if (ans >= 1e9) cout << -1 << '\n';
			else cout << ans << '\n';
		}
	}
}

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