oj.uz

Submission #761882

# Submission time Handle Problem Language Result Execution time Memory
761882 2023-06-20T10:55:59 Z jmyszka2007 Toll (BOI17_toll) C++17
7 / 100
 125 ms 17156 KB 
#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;
		a++;
		b++;
		g[a].pb({b, x});
		go[b].pb({a, x});
	}
	for(int i = 1; i <= n; i++) {
		dp[i] = 1e9;
	}
	calc(1, n);
	while(t--) {
		int a, b;
		cin >> a >> b;
		a++;
		b++;
		cout << get_ans(1, n, a, b) << '\n';
	}
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 13796 KB Output is correct
2 Correct 3 ms 4932 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 78 ms 13736 KB Output is correct
9 Correct 69 ms 13584 KB Output is correct
10 Correct 32 ms 9868 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 17156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 13796 KB Output is correct
2 Correct 3 ms 4932 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5004 KB Output is correct
5 Correct 5 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Correct 78 ms 13736 KB Output is correct
9 Correct 69 ms 13584 KB Output is correct
10 Correct 32 ms 9868 KB Output is correct
11 Incorrect 125 ms 17156 KB Output isn't correct
12 Halted 0 ms 0 KB -