Submission #1115843

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115843		vjudge1	Toll (BOI17_toll)	C++17	100 / 100	268 ms	176744 KiB

toll

#include <iostream>
using namespace std;
struct MATRIX {
	long long int a[5][5];
	MATRIX() {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 5; j++) {
				a[i][j] = 999999999;
			}
		}
	}
};
MATRIX f[50005][18];
MATRIX mul(MATRIX a, MATRIX b){
    MATRIX res;
    for (int i = 0; i < 5; i++) {
        for (int j = 0; j < 5; j++) {
            res.a[i][j] = 999999999;
            for (int k = 0; k < 5; k++) {
                res.a[i][j] = min(res.a[i][j], a.a[i][k] + b.a[k][j]);
            }
        }
    }
    return res;
}
int main() {
	int n, k, m, q;
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
    	int a, b, t;
    	cin >> a >> b >> t;
    	f[a / k][0].a[a % k][b % k] = t;
    }
    for (int i = 1; (1 << i) <= n; i++){
    	for (int j = 0; j + (1 << i) - 1 <= n; j++) {
    		f[j][i] = mul(f[j][i - 1], f[j + (1 << (i - 1))][i - 1]);
    	}
    }
    for (int jj = 0; jj < q; jj++) {
    	int a, b;
    	cin >> a >> b;
    	MATRIX s;
    	for (int j = 0; j < 5; j++) {
    		s.a[j][j] = 0;
    	}
    	if (a == b) {
    		cout << 0 << endl;
    		continue;
    	}
    	int h = a / k, g = b / k;
    	if (g <= h) {
    		cout << -1 << endl;
    	}
    	else {
    		int l = g - h;
    		for (int j = 16; j >= 0; j--) {
    			if (l & (1 << j)) {
    				s = mul(s, f[h][j]);
    				h += (1 << j);
    			}
    		}
    		if (s.a[a % k][b % k] == 999999999) cout << -1 << endl;
    		else cout << s.a[a % k][b % k] << endl;
    	}
    }
}

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