# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
761906 |
2023-06-20T11:17:10 Z |
jmyszka2007 |
Toll (BOI17_toll) |
C++17 |
|
179 ms |
25920 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;
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';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
12876 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 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 |
5052 KB |
Output is correct |
8 |
Correct |
59 ms |
12816 KB |
Output is correct |
9 |
Correct |
57 ms |
12620 KB |
Output is correct |
10 |
Correct |
26 ms |
9764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
110 ms |
15684 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5008 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
16 ms |
5216 KB |
Output is correct |
8 |
Correct |
17 ms |
5204 KB |
Output is correct |
9 |
Correct |
60 ms |
13644 KB |
Output is correct |
10 |
Correct |
134 ms |
22020 KB |
Output is correct |
11 |
Correct |
115 ms |
17300 KB |
Output is correct |
12 |
Correct |
92 ms |
19472 KB |
Output is correct |
13 |
Correct |
127 ms |
20280 KB |
Output is correct |
14 |
Correct |
78 ms |
14540 KB |
Output is correct |
15 |
Correct |
75 ms |
16732 KB |
Output is correct |
16 |
Correct |
83 ms |
16604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
4 ms |
5076 KB |
Output is correct |
8 |
Correct |
5 ms |
5332 KB |
Output is correct |
9 |
Correct |
5 ms |
5204 KB |
Output is correct |
10 |
Correct |
48 ms |
13616 KB |
Output is correct |
11 |
Correct |
79 ms |
16988 KB |
Output is correct |
12 |
Correct |
119 ms |
21808 KB |
Output is correct |
13 |
Correct |
126 ms |
22700 KB |
Output is correct |
14 |
Correct |
106 ms |
20720 KB |
Output is correct |
15 |
Correct |
70 ms |
16628 KB |
Output is correct |
16 |
Correct |
73 ms |
16620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
5000 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
5076 KB |
Output is correct |
7 |
Correct |
4 ms |
5076 KB |
Output is correct |
8 |
Correct |
5 ms |
5332 KB |
Output is correct |
9 |
Correct |
5 ms |
5204 KB |
Output is correct |
10 |
Correct |
48 ms |
13616 KB |
Output is correct |
11 |
Correct |
79 ms |
16988 KB |
Output is correct |
12 |
Correct |
119 ms |
21808 KB |
Output is correct |
13 |
Correct |
126 ms |
22700 KB |
Output is correct |
14 |
Correct |
106 ms |
20720 KB |
Output is correct |
15 |
Correct |
70 ms |
16628 KB |
Output is correct |
16 |
Correct |
73 ms |
16620 KB |
Output is correct |
17 |
Correct |
83 ms |
17020 KB |
Output is correct |
18 |
Correct |
3 ms |
5004 KB |
Output is correct |
19 |
Correct |
2 ms |
5012 KB |
Output is correct |
20 |
Correct |
2 ms |
4956 KB |
Output is correct |
21 |
Correct |
2 ms |
5012 KB |
Output is correct |
22 |
Correct |
3 ms |
4960 KB |
Output is correct |
23 |
Correct |
7 ms |
5152 KB |
Output is correct |
24 |
Correct |
8 ms |
5208 KB |
Output is correct |
25 |
Correct |
9 ms |
5344 KB |
Output is correct |
26 |
Correct |
9 ms |
5216 KB |
Output is correct |
27 |
Correct |
49 ms |
13676 KB |
Output is correct |
28 |
Correct |
121 ms |
21916 KB |
Output is correct |
29 |
Correct |
136 ms |
22760 KB |
Output is correct |
30 |
Correct |
108 ms |
20808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
64 ms |
12876 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 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 |
5052 KB |
Output is correct |
8 |
Correct |
59 ms |
12816 KB |
Output is correct |
9 |
Correct |
57 ms |
12620 KB |
Output is correct |
10 |
Correct |
26 ms |
9764 KB |
Output is correct |
11 |
Correct |
110 ms |
15684 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
5008 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
16 ms |
5216 KB |
Output is correct |
18 |
Correct |
17 ms |
5204 KB |
Output is correct |
19 |
Correct |
60 ms |
13644 KB |
Output is correct |
20 |
Correct |
134 ms |
22020 KB |
Output is correct |
21 |
Correct |
115 ms |
17300 KB |
Output is correct |
22 |
Correct |
92 ms |
19472 KB |
Output is correct |
23 |
Correct |
127 ms |
20280 KB |
Output is correct |
24 |
Correct |
78 ms |
14540 KB |
Output is correct |
25 |
Correct |
75 ms |
16732 KB |
Output is correct |
26 |
Correct |
83 ms |
16604 KB |
Output is correct |
27 |
Correct |
2 ms |
4948 KB |
Output is correct |
28 |
Correct |
2 ms |
4948 KB |
Output is correct |
29 |
Correct |
3 ms |
5000 KB |
Output is correct |
30 |
Correct |
2 ms |
4948 KB |
Output is correct |
31 |
Correct |
3 ms |
4948 KB |
Output is correct |
32 |
Correct |
3 ms |
5076 KB |
Output is correct |
33 |
Correct |
4 ms |
5076 KB |
Output is correct |
34 |
Correct |
5 ms |
5332 KB |
Output is correct |
35 |
Correct |
5 ms |
5204 KB |
Output is correct |
36 |
Correct |
48 ms |
13616 KB |
Output is correct |
37 |
Correct |
79 ms |
16988 KB |
Output is correct |
38 |
Correct |
119 ms |
21808 KB |
Output is correct |
39 |
Correct |
126 ms |
22700 KB |
Output is correct |
40 |
Correct |
106 ms |
20720 KB |
Output is correct |
41 |
Correct |
70 ms |
16628 KB |
Output is correct |
42 |
Correct |
73 ms |
16620 KB |
Output is correct |
43 |
Correct |
83 ms |
17020 KB |
Output is correct |
44 |
Correct |
3 ms |
5004 KB |
Output is correct |
45 |
Correct |
2 ms |
5012 KB |
Output is correct |
46 |
Correct |
2 ms |
4956 KB |
Output is correct |
47 |
Correct |
2 ms |
5012 KB |
Output is correct |
48 |
Correct |
3 ms |
4960 KB |
Output is correct |
49 |
Correct |
7 ms |
5152 KB |
Output is correct |
50 |
Correct |
8 ms |
5208 KB |
Output is correct |
51 |
Correct |
9 ms |
5344 KB |
Output is correct |
52 |
Correct |
9 ms |
5216 KB |
Output is correct |
53 |
Correct |
49 ms |
13676 KB |
Output is correct |
54 |
Correct |
121 ms |
21916 KB |
Output is correct |
55 |
Correct |
136 ms |
22760 KB |
Output is correct |
56 |
Correct |
108 ms |
20808 KB |
Output is correct |
57 |
Correct |
179 ms |
25920 KB |
Output is correct |
58 |
Correct |
60 ms |
13760 KB |
Output is correct |
59 |
Correct |
97 ms |
17356 KB |
Output is correct |