Submission #1237049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237049		ssitaram	Toll (BOI17_toll)	C++20	0 / 100	124 ms	46228 KiB

toll

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

typedef long long ll;
typedef long double ld;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int k, n, m, o; cin >> k >> n >> m >> o;
	vector<vector<vector<int>>> dist(n, vector<vector<int>>(16, vector<int>(k, 1e9)));
	for (int i = 0; i < m; ++i) {
		int a, b, t; cin >> a >> b >> t;
		dist[a][0][b % k] = t;
	}
	for (int i = 1; i < 16; ++i) {
		for (int a = 0; a < n; ++a) {
			for (int b = 0; b < k; ++b) {
				for (int c = 0; c < k; ++c) {
					if ((a / k + (1 << (i - 1))) * k + b < n)
					dist[a][i][c] = min(dist[a][i][c], dist[a][i - 1][b] + dist[(a / k + (1 << (i - 1))) * k + b][i - 1][c]);
				}
			}
		}
	}
	while (o--) {
		int a, b; cin >> a >> b;
		int d = b / k - a / k;
		vector<int> places(k, 1e9);
		places[a % k] = 0;
		int st = a / k * k;
		for (int i = 0; i < 16; ++i) {
			if (d & (1 << i)) {
				vector<int> nplaces(k, 1e9);
				for (int fr = 0; fr < k; ++fr) {
					for (int j = 0; j < k; ++j) {
						nplaces[j] = min(nplaces[j], places[st + fr] + dist[st + fr][i][j]);
					}
				}
				st += (1 << i) * k;
				places = nplaces;
			}
		}
		cout << (places[b % k] == 1e9 ? -1 : places[b % k]) << '\n';
	}
	return 0;
}

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