Submission #779150

#	Time	Username	Problem	Language	Result	Execution time	Memory
779150		raysh07	Toll (BOI17_toll)	C++17	100 / 100	216 ms	80716 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

vector<vector<int>> combine(vector<vector<int>> &a, vector<vector<int>> &b){
	int k = a.size();
	vector<vector<int>> res(k, vector<int>(k, INF));
	for (int i = 0; i < k; i++){
		for (int j = 0; j < k; j++){
			for (int z = 0; z < k; z++){
				res[i][j] = min(res[i][j], a[i][z] + b[z][j]);
			}
		}
	}
	return res;
}

void Solve()
{
	int k, n, m, q; cin >> k >> n >> m >> q;

	vector<vector<vector<vector<int>>>> dp((n/k) + 1, vector<vector<vector<int>>>(18, vector<vector<int>>(k, vector<int>(k, INF))));
	for (int i = 1; i <= m; i++){
		int a, b, t; cin >> a >> b >> t;

		dp[a/k][0][a % k][b % k] = t;
	}

	for (int j = 1; j < 18; j++){
		for (int i = 0; i <= n/k; i++){
			//combine dp[i][j - 1] and dp[i + (1 << (j - 1))][j - 1]
			int x = i + (1 << (j - 1));
			
			if (x <= (n/k))
			dp[i][j] = combine(dp[i][j - 1], dp[x][j - 1]);
		}
	}

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

		int x = a / k;
		int y = b / k;
		int diff = y - x;

		//lift diff times 
		vector<vector<int>> res(k, vector<int>(k, INF));
		res[a % k][a % k] = 0;

		for (int i = 17; i >= 0; i--){
			if (diff >> i & 1){
				res = combine(res, dp[x][i]);
				x += 1 << i;
			}
		}

		int ans = INF;
		for (int i = 0; i < k; i++){
			ans = min(ans, res[i][b % k]);
		}
        if (ans == INF) ans = -1;
		cout << ans << "\n";
	}
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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