oj.uz

Submission #1096167

# Submission time Handle Problem Language Result Execution time Memory
1096167 2024-10-04T03:40:16 Z sssamui Toll (BOI17_toll) C++17
0 / 100
 183 ms 78780 KB 
#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, 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 78780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 68868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 3 ms 1884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 3 ms 1884 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 183 ms 78780 KB Output isn't correct
2 Halted 0 ms 0 KB -