# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
867170 |
2023-10-27T19:38:43 Z |
bobbilyking |
Toll (BOI17_toll) |
C++17 |
|
651 ms |
16720 KB |
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
#define NN 50010
#define M 1000000007 // 998244353
constexpr ll inf = 1e18;
vector<pl> adj[NN];
vector<pl> radj[NN];
ll ans[NN], l[NN], r[NN];
ll k;
ll n;
// returns array of size r-l+1, indexed with l
vector<ll> dij(ll l, ll r, ll v, const vector<pl> (&adj)[NN]) {
vector<ll> dist(r-l+1, inf); v-=l;
dist[v] = 0;
priority_queue<pl, vector<pl>, greater<pl>> pq;
pq.emplace(dist[v], v);
while (pq.size()) {
auto [d, h] = pq.top(); pq.pop();
if (d != dist[h]) continue;
for (auto [x, w]: adj[h+l]){
if (l <= x and x <= r){
x-=l;
if (d + w < dist[x]) {
dist[x] = d + w;
pq.emplace(dist[x], x);
}
}
}
}
return dist;
}
void solve(ll lb, ll rb, vector<ll>& q) {
if (lb >= rb) return;
vector<ll> lq, rq;
ll m = (lb+rb)/2;
// All queries will pass through the roads m-k, m+k
F(thru, max(lb, m-k), min(rb, m+k)+1) {
auto out = dij(lb, rb, thru, adj);
auto in = dij(lb, rb, thru, radj);
for (auto i: q) {
// cout << "WTF ARE U DOING" << i << ": " << in[l[i]-lb] << " " << out[r[i]-lb] << endl;
ans[i] = min(ans[i], in[l[i]-lb] + out[r[i]-lb]);
}
}
for (auto i: q) {
if (r[i] < m) lq.push_back(i);
else if (m < l[i]) rq.push_back(i);
}
solve(lb, m-1, lq);
solve(m+1, rb, rq);
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
cin >> k >> n;
G(m) G(o)
vector<ll> q;
while(m--){
G(a) G(b) G(x) adj[a].emplace_back(b, x); radj[b].emplace_back(a, x);
}
F(i, 0, o) {
cin >> l[i] >> r[i]; q.push_back(i);
ans[i] = inf;
}
solve(0, n-1, q);
F(i, 0, o) {
// assert(r[i] - l[i] == ans[i]/100);
// cout << l[i] << "-> " << r[i] << ": " << (ans[i] == inf ? -1: ans[i]) << '\n';
cout << (ans[i] == inf ? -1: ans[i]) << '\n';
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
7868 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
2 ms |
3588 KB |
Output is correct |
5 |
Correct |
2 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3676 KB |
Output is correct |
7 |
Correct |
2 ms |
3932 KB |
Output is correct |
8 |
Correct |
51 ms |
8776 KB |
Output is correct |
9 |
Correct |
37 ms |
8540 KB |
Output is correct |
10 |
Correct |
12 ms |
4956 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
9884 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3676 KB |
Output is correct |
5 |
Correct |
1 ms |
3676 KB |
Output is correct |
6 |
Correct |
1 ms |
3676 KB |
Output is correct |
7 |
Correct |
4 ms |
4012 KB |
Output is correct |
8 |
Correct |
5 ms |
4184 KB |
Output is correct |
9 |
Correct |
53 ms |
7824 KB |
Output is correct |
10 |
Correct |
355 ms |
12648 KB |
Output is correct |
11 |
Correct |
190 ms |
9996 KB |
Output is correct |
12 |
Correct |
77 ms |
8976 KB |
Output is correct |
13 |
Correct |
509 ms |
13712 KB |
Output is correct |
14 |
Correct |
206 ms |
9604 KB |
Output is correct |
15 |
Correct |
263 ms |
8368 KB |
Output is correct |
16 |
Correct |
259 ms |
8328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3676 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3676 KB |
Output is correct |
5 |
Correct |
1 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3676 KB |
Output is correct |
7 |
Correct |
3 ms |
3676 KB |
Output is correct |
8 |
Correct |
11 ms |
4152 KB |
Output is correct |
9 |
Correct |
7 ms |
4032 KB |
Output is correct |
10 |
Correct |
48 ms |
7616 KB |
Output is correct |
11 |
Correct |
163 ms |
11096 KB |
Output is correct |
12 |
Correct |
386 ms |
14516 KB |
Output is correct |
13 |
Correct |
380 ms |
15680 KB |
Output is correct |
14 |
Correct |
294 ms |
12724 KB |
Output is correct |
15 |
Correct |
259 ms |
9440 KB |
Output is correct |
16 |
Correct |
260 ms |
9436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3676 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
1 ms |
3676 KB |
Output is correct |
5 |
Correct |
1 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3676 KB |
Output is correct |
7 |
Correct |
3 ms |
3676 KB |
Output is correct |
8 |
Correct |
11 ms |
4152 KB |
Output is correct |
9 |
Correct |
7 ms |
4032 KB |
Output is correct |
10 |
Correct |
48 ms |
7616 KB |
Output is correct |
11 |
Correct |
163 ms |
11096 KB |
Output is correct |
12 |
Correct |
386 ms |
14516 KB |
Output is correct |
13 |
Correct |
380 ms |
15680 KB |
Output is correct |
14 |
Correct |
294 ms |
12724 KB |
Output is correct |
15 |
Correct |
259 ms |
9440 KB |
Output is correct |
16 |
Correct |
260 ms |
9436 KB |
Output is correct |
17 |
Correct |
160 ms |
11188 KB |
Output is correct |
18 |
Correct |
1 ms |
3676 KB |
Output is correct |
19 |
Correct |
1 ms |
3676 KB |
Output is correct |
20 |
Correct |
1 ms |
3928 KB |
Output is correct |
21 |
Correct |
1 ms |
3676 KB |
Output is correct |
22 |
Correct |
1 ms |
3676 KB |
Output is correct |
23 |
Correct |
3 ms |
3928 KB |
Output is correct |
24 |
Correct |
4 ms |
3932 KB |
Output is correct |
25 |
Correct |
10 ms |
4188 KB |
Output is correct |
26 |
Correct |
8 ms |
3932 KB |
Output is correct |
27 |
Correct |
58 ms |
8760 KB |
Output is correct |
28 |
Correct |
357 ms |
14656 KB |
Output is correct |
29 |
Correct |
397 ms |
15796 KB |
Output is correct |
30 |
Correct |
282 ms |
12804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
70 ms |
7868 KB |
Output is correct |
2 |
Correct |
1 ms |
3676 KB |
Output is correct |
3 |
Correct |
1 ms |
3676 KB |
Output is correct |
4 |
Correct |
2 ms |
3588 KB |
Output is correct |
5 |
Correct |
2 ms |
3676 KB |
Output is correct |
6 |
Correct |
2 ms |
3676 KB |
Output is correct |
7 |
Correct |
2 ms |
3932 KB |
Output is correct |
8 |
Correct |
51 ms |
8776 KB |
Output is correct |
9 |
Correct |
37 ms |
8540 KB |
Output is correct |
10 |
Correct |
12 ms |
4956 KB |
Output is correct |
11 |
Correct |
164 ms |
9884 KB |
Output is correct |
12 |
Correct |
1 ms |
3676 KB |
Output is correct |
13 |
Correct |
1 ms |
3676 KB |
Output is correct |
14 |
Correct |
1 ms |
3676 KB |
Output is correct |
15 |
Correct |
1 ms |
3676 KB |
Output is correct |
16 |
Correct |
1 ms |
3676 KB |
Output is correct |
17 |
Correct |
4 ms |
4012 KB |
Output is correct |
18 |
Correct |
5 ms |
4184 KB |
Output is correct |
19 |
Correct |
53 ms |
7824 KB |
Output is correct |
20 |
Correct |
355 ms |
12648 KB |
Output is correct |
21 |
Correct |
190 ms |
9996 KB |
Output is correct |
22 |
Correct |
77 ms |
8976 KB |
Output is correct |
23 |
Correct |
509 ms |
13712 KB |
Output is correct |
24 |
Correct |
206 ms |
9604 KB |
Output is correct |
25 |
Correct |
263 ms |
8368 KB |
Output is correct |
26 |
Correct |
259 ms |
8328 KB |
Output is correct |
27 |
Correct |
2 ms |
3676 KB |
Output is correct |
28 |
Correct |
1 ms |
3676 KB |
Output is correct |
29 |
Correct |
1 ms |
3676 KB |
Output is correct |
30 |
Correct |
1 ms |
3676 KB |
Output is correct |
31 |
Correct |
1 ms |
3676 KB |
Output is correct |
32 |
Correct |
2 ms |
3676 KB |
Output is correct |
33 |
Correct |
3 ms |
3676 KB |
Output is correct |
34 |
Correct |
11 ms |
4152 KB |
Output is correct |
35 |
Correct |
7 ms |
4032 KB |
Output is correct |
36 |
Correct |
48 ms |
7616 KB |
Output is correct |
37 |
Correct |
163 ms |
11096 KB |
Output is correct |
38 |
Correct |
386 ms |
14516 KB |
Output is correct |
39 |
Correct |
380 ms |
15680 KB |
Output is correct |
40 |
Correct |
294 ms |
12724 KB |
Output is correct |
41 |
Correct |
259 ms |
9440 KB |
Output is correct |
42 |
Correct |
260 ms |
9436 KB |
Output is correct |
43 |
Correct |
160 ms |
11188 KB |
Output is correct |
44 |
Correct |
1 ms |
3676 KB |
Output is correct |
45 |
Correct |
1 ms |
3676 KB |
Output is correct |
46 |
Correct |
1 ms |
3928 KB |
Output is correct |
47 |
Correct |
1 ms |
3676 KB |
Output is correct |
48 |
Correct |
1 ms |
3676 KB |
Output is correct |
49 |
Correct |
3 ms |
3928 KB |
Output is correct |
50 |
Correct |
4 ms |
3932 KB |
Output is correct |
51 |
Correct |
10 ms |
4188 KB |
Output is correct |
52 |
Correct |
8 ms |
3932 KB |
Output is correct |
53 |
Correct |
58 ms |
8760 KB |
Output is correct |
54 |
Correct |
357 ms |
14656 KB |
Output is correct |
55 |
Correct |
397 ms |
15796 KB |
Output is correct |
56 |
Correct |
282 ms |
12804 KB |
Output is correct |
57 |
Correct |
651 ms |
16720 KB |
Output is correct |
58 |
Correct |
57 ms |
8796 KB |
Output is correct |
59 |
Correct |
175 ms |
11744 KB |
Output is correct |