Submission #758159

#	Time	Username	Problem	Language	Result	Execution time	Memory
758159		MetalPower	Toll (BOI17_toll)	C++14	100 / 100	87 ms	15948 KiB

toll

#include <bits/stdc++.h>
using namespace std;

const int MK = 5;
const int MX = 5e4 + 10;
const int INF = 1e9 + 7;

int K, N, M, Q;

void chmin(int& a, int b){
	if(b < a) a = b;
}

struct matrix{
	int arr[MK][MK];

	void init(int t = INF){
		for(int i = 0; i < K; i++){
			for(int j = 0; j < K; j++) arr[i][j] = INF;
			arr[i][i] = t;
		}
	}

	matrix operator + (const matrix& other){
		matrix c; c.init();
		for(int i = 0; i < K; i++){
			for(int j = 0; j < K; j++){
				for(int k = 0; k < K; k++){
					chmin(c.arr[i][j], arr[i][k] + other.arr[k][j]);
				}
			}
		}
		return c;
	}
};

matrix A[MX];

struct segtree{
	matrix st[MX << 1];

	void build(){
		for(int i = MX; i < (MX << 1); i++) st[i] = A[i - MX];
		for(int i = MX - 1; i > 0; i--) st[i] = st[i << 1] + st[i << 1|1];
	}

	matrix que(int l, int r){
		matrix lf, rg; lf.init(0); rg.init(0);
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) lf = lf + st[l], l++;
			if(r & 1) --r, rg = st[r] + rg;
		}
		lf = lf + rg;
		return lf;
	}
} S;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> K >> N >> M >> Q;
	for(int i = 0; i < (N - 1) / K; i++) A[i].init();
	for(int i = 0; i < M; i++){
		int a, b, t; cin >> a >> b >> t;
		chmin(A[a / K].arr[a % K][b % K], t);
	}

	S.build();
	for(int i = 0; i < Q; i++){
		int a, b; cin >> a >> b;
		if(a / K == b / K){
			cout << -1 << '\n';
			continue;
		}
		matrix ans = S.que(a / K, b / K - 1);
		if(ans.arr[a % K][b % K] == INF) cout << -1 << '\n';
		else cout << ans.arr[a % K][b % K] << '\n';
	}
}

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