제출 #441852

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
441852		dutch	Toll (BOI17_toll)	C++17	100 / 100	200 ms	28364 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define int long long
using T = array<array<int, 5>, 6>;

const int MAXN = 1e5, INF = 1e16;

vector<array<int, 2>> g[MAXN];
int n, k, m, o, s;
T ID, a[1<<17];

T comb(T x, T y){
	if(x[5][0] > y[5][0]) swap(x, y);
	int z = y[5][0];
	if(z == INF) return x;
	T res = ID;
	res[5][0] = x[5][0];
	for(int i=0; i<k; ++i)
		for(int u=0; u<k; ++u)
			for(auto &[v, w] : g[(z-1)*k+u])
				for(int j=0; j<k; ++j)
					res[i][j] = min(res[i][j], x[i][u] + w + y[v%k][j]);
	return res;
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> k >> n >> m >> o;
	while(m--){
		int u, v, w; cin >> u >> v >> w;
		g[u].push_back({v, w});
	}

	for(int i=0; i<6; ++i) for(int j=0; j<5; ++j) ID[i][j] = (i!=j) * INF;
	s = (n + k - 1) / k;
	fill(a, a+2*s, ID);
	for(int i=0; i<s; ++i) a[i+s][5][0] = i;
	for(int i=0; i<5; ++i) ID[i][i] = INF;
	for(int i=s; --i; ) a[i] = comb(a[2*i], a[2*i+1]);

	while(o--){
		int i, j; cin >> i >> j;

		int l = i/k, r = j/k;
		T lx = ID, rx = ID;
		for(l+=s, r+=s+1; l<r; l/=2, r/=2){
			if(l & 1) lx = comb(lx, a[l++]);
			if(r & 1) rx = comb(rx, a[--r]);
		}
		i = comb(lx, rx)[i % k][j % k];

		cout << (i == INF ? -1 : i) << '\n';
	}
}

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