Submission #761906

#	Time	Username	Problem	Language	Result	Execution time	Memory
761906		jmyszka2007	Toll (BOI17_toll)	C++17	100 / 100	179 ms	25920 KiB

toll

#include <bits/stdc++.h>
using namespace std;
#define pi pair<int, int>
#define st first
#define nd second
#define vi vector<int>
#define pb push_back
constexpr int LIM = 50'000;
vector<pi>g[LIM + 10];
vector<pi>go[LIM + 10];
int dp[LIM + 10];
vi lft[LIM + 10];
vi rgt[LIM + 10];
int k;
void calc(int l, int r) {
	if(l / k >= r / k) {
		return;
	}
	int mid = ((r / k) + (l / k)) / 2;
	for(int i = mid * k; i < (mid + 1) * k; i++) {
		dp[i] = 0;
		for(int j = mid * k - 1; j >= l; j--) {
			for(auto x : g[j]) {
				dp[j] = min(dp[j], dp[x.st] + x.nd);
			
			}
			lft[i].pb(dp[j]);
		}
		dp[i] = 1e9;
		for(int j = mid * k - 1; j >= l; j--) {
			dp[j] = 1e9;
		}
	}
	for(int i = mid * k; i < (mid + 1) * k; i++) {
		dp[i] = 0;
		for(int j = (mid + 1) * k; j <= r; j++) {
			for(auto x : go[j]) {
				dp[j] = min(dp[j], dp[x.st] + x.nd);
			}
			rgt[i].pb(dp[j]);
		}
		dp[i] = 1e9;
		for(int j = (mid + 1) * k; j <= r; j++) {
			dp[j] = 1e9;
		}
	}
	calc(l, mid * k - 1);
	calc((mid + 1) * k, r);
}
int get_ans(int l, int r, int a, int b) {
	if(a / k >= b / k) {
		return -1;
	}
	int mid = ((r / k) + (l / k)) / 2;
	//cout << l << ' ' << r << '\n';
	//cout << a << ' ' << mid << ' ' << b << '\n';
	if(a / k <= mid && mid <= b / k) {
		int ans = 1e9;
		if(a / k == mid) {
			ans = rgt[a][b - (mid + 1) * k];
		}
		else if(b / k == mid) {
			ans = lft[b][mid * k - 1 - a];
		}
		else {
			for(int i = mid * k; i < (mid + 1) * k; i++) {
				ans = min(ans, lft[i][mid * k - 1 - a] + rgt[i][b - ((mid + 1) * k)]);
			}
		}
		if(ans >= 1e9) {
			return -1;
		}
		else {
			return ans;
		} 
	}
	if(a / k > mid) {
		return get_ans((mid + 1) * k, r, a, b);
	}
	else {
		return get_ans(l, mid * k - 1, a, b);
	}
}
int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	int n, m, t;
	cin >> k >> n >> m >> t;
	for(int i = 1; i <= m; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		g[a].pb({b, x});
		go[b].pb({a, x});
	}
	for(int i = 0; i < n; i++) {
		dp[i] = 1e9;
	}
	calc(0, n - 1);
	while(t--) {
		int a, b;
		cin >> a >> b;
		cout << get_ans(0, n - 1, a, b) << '\n';
	}
}

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