# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
667241 |
2022-11-30T21:37:23 Z |
Sogol |
Toll (BOI17_toll) |
C++17 |
|
225 ms |
147528 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define Sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
const int maxn = 1e6 + 10;
const int maxa = 2e9 + 5;
const int mod = 1e9 + 7;
const ll inf = 2e18;
const double eps = 1e-9;
int a[maxn], b[maxn], dp[maxn], pd[maxn], ans[maxn], n, k, bl;
vector <pair <int, int> > adj[maxn], ajd[maxn];
vector <int> qu[4 * maxn];
void avocado(int nd = 1, int s = 0, int e = bl){
if (e - s == 1) return;
int mid = (s + e) / 2, lc = 2 * nd, rc = lc + 1;
avocado(lc, s, mid);
avocado(rc, mid, e);
for (int i = 0; i < k; i ++){
int v = mid * k + i;
if(v >= n) break;
fill(dp + s * k, dp + e * k, mod);
fill(pd + s * k, pd + e * k, mod);
dp[v] = 0;
for (int j = v; j < k * e; j ++){
for (auto p : adj[j]){
int u = p.fi, w = p.se;
dp[u] = min(dp[u], dp[j] + w);
}
}
pd[v] = 0;
for (int j = v; j >= s * k; j --){
for (auto p : ajd[j]){
int u = p.fi, w = p.se;
pd[u] = min(pd[u], pd[j] + w);
}
}
for (int x : qu[nd]){
ans[x] = min(ans[x], pd[a[x]] + dp[b[x]]);
}
}
return;
}
int find(int l, int r, int v = 1, int s = 0, int e = bl){
if(e - s == 1) return v;
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
if(r <= mid) return find(l, r, lc, s, mid);
if(mid < l) return find(l, r, rc, mid, e);
return v;
}
int main(){
ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int m, o;
cin >> k >> n >> m >> o;
bl = (n + k - 1) / k;
for (int i = 0; i < m; i ++){
int v, u, t;
cin >> v >> u >> t;
adj[v].pb({u, t});
ajd[u].pb({v, t});
}
fill(ans, ans + o, mod);
for (int i = 0; i < o; i ++){
cin >> a[i] >> b[i];
if(a[i] > b[i]) continue;
qu[find(a[i] / k, b[i] / k + 1)].pb(i);
}
avocado();
for (int i = 0; i < o; i ++) cout << (ans[i] >= mod ? -1 : ans[i]) << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
145100 KB |
Output is correct |
2 |
Correct |
72 ms |
141168 KB |
Output is correct |
3 |
Correct |
66 ms |
141136 KB |
Output is correct |
4 |
Correct |
75 ms |
141116 KB |
Output is correct |
5 |
Correct |
68 ms |
141352 KB |
Output is correct |
6 |
Correct |
73 ms |
141360 KB |
Output is correct |
7 |
Correct |
70 ms |
141360 KB |
Output is correct |
8 |
Correct |
111 ms |
145228 KB |
Output is correct |
9 |
Correct |
103 ms |
144884 KB |
Output is correct |
10 |
Correct |
73 ms |
141904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
145 ms |
145028 KB |
Output is correct |
2 |
Correct |
71 ms |
141228 KB |
Output is correct |
3 |
Correct |
70 ms |
141204 KB |
Output is correct |
4 |
Correct |
67 ms |
141132 KB |
Output is correct |
5 |
Correct |
68 ms |
141236 KB |
Output is correct |
6 |
Correct |
69 ms |
141216 KB |
Output is correct |
7 |
Correct |
76 ms |
141604 KB |
Output is correct |
8 |
Correct |
73 ms |
141556 KB |
Output is correct |
9 |
Correct |
102 ms |
145188 KB |
Output is correct |
10 |
Correct |
166 ms |
146976 KB |
Output is correct |
11 |
Correct |
148 ms |
145344 KB |
Output is correct |
12 |
Correct |
133 ms |
145020 KB |
Output is correct |
13 |
Correct |
192 ms |
147152 KB |
Output is correct |
14 |
Correct |
131 ms |
144984 KB |
Output is correct |
15 |
Correct |
132 ms |
144328 KB |
Output is correct |
16 |
Correct |
139 ms |
144556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
141132 KB |
Output is correct |
2 |
Correct |
67 ms |
141156 KB |
Output is correct |
3 |
Correct |
72 ms |
141132 KB |
Output is correct |
4 |
Correct |
75 ms |
141144 KB |
Output is correct |
5 |
Correct |
72 ms |
141236 KB |
Output is correct |
6 |
Correct |
70 ms |
141328 KB |
Output is correct |
7 |
Correct |
71 ms |
141356 KB |
Output is correct |
8 |
Correct |
73 ms |
141436 KB |
Output is correct |
9 |
Correct |
73 ms |
141360 KB |
Output is correct |
10 |
Correct |
121 ms |
144924 KB |
Output is correct |
11 |
Correct |
134 ms |
145020 KB |
Output is correct |
12 |
Correct |
187 ms |
146952 KB |
Output is correct |
13 |
Correct |
202 ms |
147288 KB |
Output is correct |
14 |
Correct |
147 ms |
146088 KB |
Output is correct |
15 |
Correct |
133 ms |
144344 KB |
Output is correct |
16 |
Correct |
140 ms |
144352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
141132 KB |
Output is correct |
2 |
Correct |
67 ms |
141156 KB |
Output is correct |
3 |
Correct |
72 ms |
141132 KB |
Output is correct |
4 |
Correct |
75 ms |
141144 KB |
Output is correct |
5 |
Correct |
72 ms |
141236 KB |
Output is correct |
6 |
Correct |
70 ms |
141328 KB |
Output is correct |
7 |
Correct |
71 ms |
141356 KB |
Output is correct |
8 |
Correct |
73 ms |
141436 KB |
Output is correct |
9 |
Correct |
73 ms |
141360 KB |
Output is correct |
10 |
Correct |
121 ms |
144924 KB |
Output is correct |
11 |
Correct |
134 ms |
145020 KB |
Output is correct |
12 |
Correct |
187 ms |
146952 KB |
Output is correct |
13 |
Correct |
202 ms |
147288 KB |
Output is correct |
14 |
Correct |
147 ms |
146088 KB |
Output is correct |
15 |
Correct |
133 ms |
144344 KB |
Output is correct |
16 |
Correct |
140 ms |
144352 KB |
Output is correct |
17 |
Correct |
130 ms |
145196 KB |
Output is correct |
18 |
Correct |
68 ms |
141244 KB |
Output is correct |
19 |
Correct |
74 ms |
141232 KB |
Output is correct |
20 |
Correct |
86 ms |
141268 KB |
Output is correct |
21 |
Correct |
69 ms |
141212 KB |
Output is correct |
22 |
Correct |
70 ms |
141204 KB |
Output is correct |
23 |
Correct |
70 ms |
141300 KB |
Output is correct |
24 |
Correct |
73 ms |
141384 KB |
Output is correct |
25 |
Correct |
74 ms |
141488 KB |
Output is correct |
26 |
Correct |
70 ms |
141452 KB |
Output is correct |
27 |
Correct |
107 ms |
145060 KB |
Output is correct |
28 |
Correct |
169 ms |
146844 KB |
Output is correct |
29 |
Correct |
183 ms |
147244 KB |
Output is correct |
30 |
Correct |
172 ms |
146144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
145100 KB |
Output is correct |
2 |
Correct |
72 ms |
141168 KB |
Output is correct |
3 |
Correct |
66 ms |
141136 KB |
Output is correct |
4 |
Correct |
75 ms |
141116 KB |
Output is correct |
5 |
Correct |
68 ms |
141352 KB |
Output is correct |
6 |
Correct |
73 ms |
141360 KB |
Output is correct |
7 |
Correct |
70 ms |
141360 KB |
Output is correct |
8 |
Correct |
111 ms |
145228 KB |
Output is correct |
9 |
Correct |
103 ms |
144884 KB |
Output is correct |
10 |
Correct |
73 ms |
141904 KB |
Output is correct |
11 |
Correct |
145 ms |
145028 KB |
Output is correct |
12 |
Correct |
71 ms |
141228 KB |
Output is correct |
13 |
Correct |
70 ms |
141204 KB |
Output is correct |
14 |
Correct |
67 ms |
141132 KB |
Output is correct |
15 |
Correct |
68 ms |
141236 KB |
Output is correct |
16 |
Correct |
69 ms |
141216 KB |
Output is correct |
17 |
Correct |
76 ms |
141604 KB |
Output is correct |
18 |
Correct |
73 ms |
141556 KB |
Output is correct |
19 |
Correct |
102 ms |
145188 KB |
Output is correct |
20 |
Correct |
166 ms |
146976 KB |
Output is correct |
21 |
Correct |
148 ms |
145344 KB |
Output is correct |
22 |
Correct |
133 ms |
145020 KB |
Output is correct |
23 |
Correct |
192 ms |
147152 KB |
Output is correct |
24 |
Correct |
131 ms |
144984 KB |
Output is correct |
25 |
Correct |
132 ms |
144328 KB |
Output is correct |
26 |
Correct |
139 ms |
144556 KB |
Output is correct |
27 |
Correct |
68 ms |
141132 KB |
Output is correct |
28 |
Correct |
67 ms |
141156 KB |
Output is correct |
29 |
Correct |
72 ms |
141132 KB |
Output is correct |
30 |
Correct |
75 ms |
141144 KB |
Output is correct |
31 |
Correct |
72 ms |
141236 KB |
Output is correct |
32 |
Correct |
70 ms |
141328 KB |
Output is correct |
33 |
Correct |
71 ms |
141356 KB |
Output is correct |
34 |
Correct |
73 ms |
141436 KB |
Output is correct |
35 |
Correct |
73 ms |
141360 KB |
Output is correct |
36 |
Correct |
121 ms |
144924 KB |
Output is correct |
37 |
Correct |
134 ms |
145020 KB |
Output is correct |
38 |
Correct |
187 ms |
146952 KB |
Output is correct |
39 |
Correct |
202 ms |
147288 KB |
Output is correct |
40 |
Correct |
147 ms |
146088 KB |
Output is correct |
41 |
Correct |
133 ms |
144344 KB |
Output is correct |
42 |
Correct |
140 ms |
144352 KB |
Output is correct |
43 |
Correct |
130 ms |
145196 KB |
Output is correct |
44 |
Correct |
68 ms |
141244 KB |
Output is correct |
45 |
Correct |
74 ms |
141232 KB |
Output is correct |
46 |
Correct |
86 ms |
141268 KB |
Output is correct |
47 |
Correct |
69 ms |
141212 KB |
Output is correct |
48 |
Correct |
70 ms |
141204 KB |
Output is correct |
49 |
Correct |
70 ms |
141300 KB |
Output is correct |
50 |
Correct |
73 ms |
141384 KB |
Output is correct |
51 |
Correct |
74 ms |
141488 KB |
Output is correct |
52 |
Correct |
70 ms |
141452 KB |
Output is correct |
53 |
Correct |
107 ms |
145060 KB |
Output is correct |
54 |
Correct |
169 ms |
146844 KB |
Output is correct |
55 |
Correct |
183 ms |
147244 KB |
Output is correct |
56 |
Correct |
172 ms |
146144 KB |
Output is correct |
57 |
Correct |
225 ms |
147528 KB |
Output is correct |
58 |
Correct |
102 ms |
145240 KB |
Output is correct |
59 |
Correct |
136 ms |
145188 KB |
Output is correct |