Submission #441832

#	Time	Username	Problem	Language	Result	Execution time	Memory
441832		dutch	Toll (BOI17_toll)	C++17	100 / 100	228 ms	30788 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

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

vector<array<int, 2>> g[MAXN];
int n, k, m, o;

struct SegmentTree{
	using T = array<array<int, 5>, 5>;
	int sz = 1, l, r;
	vector<T> a; T ID, NA;
	T comb(const T &x, const T &y, int z){
		if(x == NA) return y;
		if(y == NA) return x;
		T res = ID;
		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;
	}
	void init(){
		int N = (n + k - 1) / k;
		while((sz+=sz)<N);
		for(int i=0; i<5; ++i)
			ID[i] = {INF, INF, INF, INF, INF};
		for(int i=0; i<5; ++i)
			NA[i] = {-1, -1, -1, -1, -1};
		a.assign(2*sz, ID);
		build(0, 0, sz);
	}
	void build(int x, int lx, int rx){
		if(rx - lx == 1){
			for(int i=0; lx*k+i<n && i<k; ++i) a[x][i][i] = 0;
			return;
		}
		int mx = (lx + rx) / 2;
		build(2*x+1, lx, mx);
		build(2*x+2, mx, rx);
		if(mx >= n) a[x] = a[2*x+1];
		else a[x] = comb(a[2*x+1], a[2*x+2], mx);
	}
	T query(int x, int lx, int rx){
		if(r<=lx || rx<=l) return NA;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return comb(query(2*x+1, lx, mx), query(2*x+2, mx, rx), mx);
	}
	int query(int L, int R){
		l = L/k, r = R/k+1;
		return query(0, 0, sz)[L%k][R%k];
	}
};

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});
	}

	SegmentTree st;
	st.init();

	while(o--){
		int l, r; cin >> l >> r;
		l = st.query(l, r);
		cout << (l == INF ? -1 : l) << '\n';
	}
}

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