Submission #1068603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068603		Thunnus	Toll (BOI17_toll)	C++17	100 / 100	62 ms	86980 KiB

toll

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
//#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int LG = 17, MAXK = 5, MX = 5e4, inf = 0x3f;
int dp[MX][LG][MAXK][MAXK], ans[MAXK][MAXK], temp[MAXK][MAXK], k;

inline void combine(int target[MAXK][MAXK], int a[MAXK][MAXK], int b[MAXK][MAXK]){
	for(int x = 0; x < k; x++){
		for(int y = 0; y < k; y++){
			for(int z = 0; z < k; z++){
				target[x][y] = min(target[x][y], a[x][z] + b[z][y]);
			}
		}
	}
}

void solve(){
	int n, m, o, a, b, t;
	cin >> k >> n >> m >> o;
	memset(dp, inf, sizeof(dp));
	while(m--){
		cin >> a >> b >> t;
		dp[a / k][0][a % k][b % k] = t;
	}
	for(int j = 1; j < LG; j++){
		for(int i = 0; i + (1ll << j) < (n + k - 1) / k; i++){
			combine(dp[i][j], dp[i][j - 1], dp[i + (1ll << (j - 1))][j - 1]);
		}
	}

	while(o--){
		cin >> a >> b;
		memset(ans, inf, sizeof(ans));
		for(int i = 0; i < MAXK; i++) ans[i][i] = 0;
		for(int cur = a / k, dest = b / k, i = LG - 1; ~i; i--){
			if(cur + (1ll << i) <= dest){
				memset(temp, inf, sizeof(temp));
				combine(temp, ans, dp[cur][i]);
				memcpy(ans, temp, sizeof(ans));
				cur += (1ll << i);
			}
		}
		cout << (ans[a % k][b % k] == 0x3f3f3f3f ? -1 : ans[a % k][b % k]) << "\n";
	}
	return;
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

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