제출 #388159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
388159		Nima_Naderi	Toll (BOI17_toll)	C++14	100 / 100	316 ms	175656 KiB

toll

//In the name of God
#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
using namespace std;

typedef long long ll;
const ll MXN = 5e4 + 10;
const ll MXS = MXN * 4;
const ll MXZ = 10;
const ll INF = 1e10;
struct Matrix{
	ll n, m;
	ll M[MXZ][MXZ];
	Matrix(ll _n = 0, ll _m = 0, ll f = 0){
		n = _n, m = _m;
		for(int i = 0; i < n; i ++){
			for(int j = 0; j < m; j ++){
				if(f == -1) M[i][j] = (i == j ? 0 : INF);
				else M[i][j] = f;
			}
		}
	}
	void Print(){
		cout << "======= N.N =======\n";
		for(int i = 0; i < n; i ++, cout << '\n'){
			for(int j = 0; j < m; j ++) cout << M[i][j] << ' ';
		}
		cout << "======= N.N =======\n";
	}
	Matrix operator * (const Matrix &T){
		assert(m == T.n);
		Matrix R = Matrix(n, T.m, INF);
		for(int i = 0; i < n; i ++){
			for(int k = 0; k < m; k ++){
				for(int j = 0; j < T.m; j ++){
					R.M[i][j] = min(R.M[i][j], M[i][k] + T.M[k][j]);
				}
			}
		}
		return R;
	}
};
ll k, n, m, q;
ll ANS[MXN];
vector<pair<ll, ll>> adj[MXN], adt[MXN], Q[MXN];
Matrix seg[MXS], Now, Res, lz, base[MXZ];
void Build(ll id = 1, ll s = 1, ll e = n){
	seg[id] = Matrix(k, k, -1);
	if(ln > 1){
		Build(lc, s, md), Build(rc, dm, e);
	}
}
void Set(ll p, ll id = 1, ll s = 1, ll e = n){
	if(e < p || s > p) return;
	if(ln == 1){
		seg[id] = Now; return;
	}
	Set(p, lc, s, md), Set(p, rc, dm, e);
	//seg[id] = seg[lc] * seg[rc];
	seg[id] = seg[rc] * seg[lc];
}
void fetch(ll l, ll r, ll id = 1, ll s = 1, ll e = n){
	if(e < l || s > r) return;
	if(l <= s && e <= r){
		//lz = lz * seg[id];
		lz = seg[id] * lz;
		return;
	}
	fetch(l, r, lc, s, md), fetch(l, r, rc, dm, e);
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> k >> n >> m >> q;
	for(int i = 0; i < m; i ++){
		ll u, v, w; cin >> u >> v >> w;
		u ++, v ++;
		adj[u].push_back({v, w});
		adt[v].push_back({u, w});
	}
	for(int i = 0; i < q; i ++){
		ll u, v; cin >> u >> v; u ++, v ++;
		Q[v].push_back({u, i});
	}
	Build();
	for(int i = 0; i < k; i ++) base[i] = Matrix(k, 1, INF), base[i].M[i][0] = 0;
	for(int f = 0; f <= (n - 1) / k; f ++){
		ll s = f * k + 1, e = min((f + 1) * k, n);
		if(f){
			Now = Matrix(k, k, INF);
			for(int v = s; v <= e; v ++){
				for(auto X : adt[v]){
					ll u, w; tie(u, w) = X;
					ll vp = (v - 1) % k, up = (u - 1) % k;
					Now.M[vp][up] = min(Now.M[vp][up], w);
				}
			}
			Set(s - 1);
		}
		for(int v = s; v <= e; v ++){
			for(auto X : Q[v]){
				ll u, id; tie(u, id) = X;
				Res = base[(u - 1) % k];
				lz = Matrix(k, k, -1); fetch(u, n);
				Res = lz * Res;
				ANS[id] = Res.M[(v - 1) % k][0];
			}
		}
	}
	for(int i = 0; i < q; i ++) cout << (ANS[i] == INF ? -1 : ANS[i]) << '\n';
	//cout << "Ok\n";
	return 0;
}
//! This is NIMA !

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