Submission #1236988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236988		ssitaram	Toll (BOI17_toll)	C++20	7 / 100	171 ms	46516 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<pair<int, int>> places = {{a, 0}};
		for (int i = 0; i < 16; ++i) {
			if (d & (1 << i)) {
				vector<pair<int, int>> nplaces;
				for (pair<int, int> fr : places) {
					for (int j = 0; j < k; ++j) {
						nplaces.push_back({(fr.first / k + (1 << i)) * k + j, min(fr.second + dist[fr.first][i][j], (int) 1e9)});
					}
				}
				places = nplaces;
			}
		}
		int ans = 1e9;
		for (pair<int, int> i : places) {
			if (i.first == b) {
				ans = i.second;
			}
		}
		cout << (ans == 1e9 ? -1 : ans) << '\n';
	}
	return 0;
}

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