Submission #1096168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096168		sssamui	Toll (BOI17_toll)	C++17	0 / 100	180 ms	78800 KiB

toll

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const int INF = 1e9;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int k, n, m, _;
	cin >> k >> n >> m >> _;
	n--;
	n /= k;
	vector<vector<vector<vector<int>>>> blft(1, vector<vector<vector<int>>>(n + 1, vector<vector<int>>(k, vector<int>(k, INF))));
	while (m--)
	{
		int a, b, d;
		cin >> a >> b >> d;
		blft[0][a / k][a % k][b % k] = d;
	}

	int K = 16;
	int pw = 1;
	while (K--)
	{
		vector<vector<vector<int>>> bck(n + 1, vector<vector<int>>(k, vector<int>(k, INF)));
		for (int i = 2 * pw; i <= n; i++) for (int s = 0; s < k; s++) for (int f = 0; f < k; f++) for (int M = 0; M < k; M++) bck[i - 2 * pw][s][f] =
			fmin(bck[i - 2 * pw][s][f], blft.back()[i - 2 * pw][s][M] + blft.back()[i - pw][M][f]);
		blft.push_back(bck);
	}

	while (_--)
	{
		int a, b;
		cin >> a >> b;

		vector<int> ans(k, INF);
		int d = (b / k) - (a / k);
		int cstt = a / k;
		ans[a % k] = 0;
		for (int i = 0; i < blft.size(); i++) if (d & (1 << i))
		{
			vector<int> nans(k, INF);
			for (int fnl = 0; fnl < k; fnl++) for (int stt = 0; stt < k; stt++) nans[fnl] = fmin(nans[fnl], ans[stt] + blft[i][cstt][stt][fnl]);
			ans = nans, cstt += (1 << i);
		}

		if (ans[b % k] == INF) cout << "-1\n";
		else cout << ans[b % k] << "\n";
	}
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<std::vector<int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int i = 0; i < blft.size(); i++) if (d & (1 << i))
      |                   ~~^~~~~~~~~~~~~

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