Submission #435716

#	Time	Username	Problem	Language	Result	Execution time	Memory
435716		penguinhacker	Toll (BOI17_toll)	C++14	100 / 100	192 ms	13512 KiB

toll

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

#define ll long long
#define ar array

const int mxN=5e4, mxQ=1e4;
int n, m, k, q, ans[mxQ];
ar<int, 2> qry[mxQ];
vector<ar<int, 2>> bef[mxN], aft[mxN];
int tl[mxN][5], tr[mxN][5];

void smin(int& x, int y) {
	if (x==-1||y<x)
		x=y;
}

void solve(int l, int r, vector<int>& v) {
	if (v.empty())
		return;
	assert(l^r);
	int mid=(l+r)/2;
	for (int i=mid*k; i<(mid+1)*k; ++i) {
		memset(tl[i], -1, sizeof(tl[i]));
		memset(tr[i], -1, sizeof(tr[i]));
		tl[i][i%k]=tr[i][i%k]=0;
	}
	for (int i=mid*k-1; i>=l*k; --i) {
		memset(tl[i], -1, sizeof(tl[i]));
		for (int j=0; j<k; ++j)
			for (ar<int, 2> a : aft[i])
				if (tl[a[0]][j]^-1)
					smin(tl[i][j], tl[a[0]][j]+a[1]);
	}
	for (int i=(mid+1)*k; i<min(n, (r+1)*k); ++i) {
		memset(tr[i], -1, sizeof(tr[i]));
		for (int j=0; j<k; ++j)
			for (ar<int, 2> a : bef[i])
				if (tr[a[0]][j]^-1)
					smin(tr[i][j], tr[a[0]][j]+a[1]);
	}
	vector<int> vl, vr;
	for (int i : v) {
		int ql=qry[i][0], qr=qry[i][1];
		assert(l*k<=ql&&qr<(r+1)*k);
		if (qr/k<mid)
			vl.push_back(i);
		else if (ql/k>mid)
			vr.push_back(i);
		else {
			ans[i]=-1;
			for (int j=0; j<k; ++j)
				if (tl[ql][j]^-1&&tr[qr][j]^-1)
					smin(ans[i], tl[ql][j]+tr[qr][j]);
		}
	}
	vector<int>().swap(v);
	solve(l, mid-1, vl);
	solve(mid+1, r, vr);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> k >> n >> m >> q;
	for (int i=0; i<m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		aft[u].push_back({v, w});
		bef[v].push_back({u, w});
	}
	vector<int> inds;
	for (int i=0; i<q; ++i) {
		cin >> qry[i][0] >> qry[i][1];
		if (qry[i][0]/k==qry[i][1]/k)
			ans[i]=-1;
		else
			inds.push_back(i);
	}
	solve(0, (n-1)/k, inds);
	for (int i=0; i<q; ++i)
		cout << ans[i] << "\n";
	return 0;
}

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