Submission #1093553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093553		coldbr3w	Toll (BOI17_toll)	C++17	0 / 100	196 ms	157264 KiB

toll

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

#define ll int
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 5e4 + 100;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const ll block = 450;
ll k,n,m,q;
struct Matrix{
	vector<vector<ll>>d;
	ll n,m;
	void init(ll _n, ll _m){
		n = _n;
		m = _m;
		d.resize(n, vector<ll>(m));
	}
	ll col() const{
		return m;
	}
	ll row() const{
		return n;
	}
};
Matrix operator* (const Matrix &a, const Matrix &b){
	Matrix ans;
	ans.init(a.row(), b.col());
	for(int i = 0; i < a.row();i++){
		for(int j = 0; j < b.col();j++) ans.d[i][j] = inf;
	}
	for(int i = 0; i < a.row(); i++){
		for(int j = 0; j < b.col();j++){
			for(int k = 0; k < a.col();k++){
				ans.d[i][j] = min(ans.d[i][j], a.d[i][k] + b.d[k][j]);
			}
		}
	}
	return ans;
}
Matrix t[N];
Matrix st[N][17];
void to_thic_cau(){
	cin >> k >> n >> m >> q;
	ll lim = (n - 1) / k;
	for(int i = 0; i <= lim;i++){
		t[i].init(k, k);
		for(int j = 0; j < k;j++){
			for(int x = 0; x < k;x++) t[i].d[j][x] = inf;
		}
	}
	for(int i = 1; i <= m;i++){
		ll u,v,w; cin >> u >> v >> w;
		t[v / k].d[u % k][v % k] = w;
	}
	for(int i = 0; i <= lim;i++) st[i][0] = t[i];
	for(int j = 1; j <= lim;j++){
		for(int i = 0; i + (1 << j) <= lim + 1;i++) st[i][j] = st[i][j-1] * st[i + (1 << (j - 1))][j-1]; 
	}
	while(q--){
		ll a,b; cin >> a >> b;
		if(a / k == b / k){
			if(a != b){
				cout << -1 << "\n";
			}
			else cout << 0 << '\n';
			continue;
		}
		ll l = a / k + 1, r = b / k;
		Matrix cur; 
		cur.init(1, k);
		for(int i = 0; i < k;i++) cur.d[0][i] = inf;
		cur.d[0][a % k] = 0;
		ll d = r - l + 1;
		for(int i = 16; i >= 0;i--){
			if(d & (1 << i)){
				assert(l <= lim);
				cur = cur * st[l][i];
				l += (1 << i);
			}
		}
		if(cur.d[0][b % k] >= 1e9){
			cout << -1 << "\n";
		}
		else cout << cur.d[0][b % k] << "\n";
	}
}   

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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