QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#168970#5458. Shortest Path QuerysyksykCCCAC ✓113ms12248kbC++142.0kb2023-09-09 08:58:302023-09-09 08:58:30

Judging History

你现在查看的是测评时间为 2023-09-09 08:58:30 的历史记录

  • [2024-06-21 12:38:17]
  • 管理员手动重测本题所有提交记录
  • 测评结果:AC
  • 用时:118ms
  • 内存:12352kb
  • [2023-09-09 08:58:30]
  • 评测
  • 测评结果:100
  • 用时:113ms
  • 内存:12248kb
  • [2023-09-09 08:58:30]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<pair<int, int>> vpii;
const int N = 5e4 + 5, M = 1e5 + 5, R = 1023;
vpii G[N], conv[R + 1]; // (w = 0, w = 1)
struct query { ll u, a, b, id, ans; } Q[N]; 
int n, m, q;
void add(vpii &c, int x, int y) {
	if(c.empty()) { c.emplace_back(x, y); return; }
	if(c.back().second <= y) return;
	if(c.back().first == x)	y = min(c.back().second, y), c.pop_back();
	while(c.size() > 1) {
		int e = (int)c.size() - 1;
		if((ll)(c[e-1].second - c[e].second) * (c[e-1].first - x) 
			>= (ll)(c[e-1].second - y) * (c[e-1].first - c[e].first)) c.pop_back();
		else break;
	}
	c.emplace_back(x, y);
}
vpii merge(const vpii &A, const vpii &B, int dx, int dy) {
	int i = 0, j = 0;
	vpii res;
	while(i < A.size() && j < B.size()) {
		if(A[i].first <= B[j].first + dx) add(res, A[i].first, A[i].second), i++;
		else add(res, B[j].first + dx, B[j].second + dy), j++;
	}
	for(; i < A.size(); i++) add(res, A[i].first, A[i].second);
	for(; j < B.size(); j++) add(res, B[j].first + dx, B[j].second + dy);
	return res;
}
int main() {
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int u, v, c;
		scanf("%d %d %d", &u, &v, &c);
		G[v].emplace_back(u, c); // reversed edge
	}
	scanf("%d", &q);
	for(int i = 1; i <= q; i++) {
		scanf("%lld %lld %lld", &Q[i].a, &Q[i].b, &Q[i].u);
		Q[i].id = i;
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.u < B.u; });
	conv[1].emplace_back(0, 0);
	int cur = 1;
	for(int u = 1; u <= n; u++) {
		if(u > R) conv[u & R].clear();
		for(auto e : G[u]) {
			int v = e.first, w = e.second;
			conv[u & R] = merge(conv[u & R], conv[v & R], w == 0, w == 1);
		}
		while(cur <= q && Q[cur].u == u) {
			ll ans = LLONG_MAX;
			for(auto p : conv[u & R]) {
				ans = min(ans, p.first * Q[cur].a + p.second * Q[cur].b);
			}
			Q[cur++].ans = ans;
		}
	}
	sort(Q + 1, Q + q + 1, [&](const query &A, const query &B){ return A.id < B.id; });
	for(int i = 1; i <= q; i++) printf("%lld\n", Q[i].ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5008kb

input:

4 4
1 2 0
1 3 1
2 4 0
3 4 1
3
3 5 2
3 2 4
2 3 4

output:

3
4
4

result:

ok 3 number(s): "3 4 4"

Test #2:

score: 0
Accepted
time: 50ms
memory: 9300kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 1
6 7 0
7 8 1
8 9 1
9 10 0
10 11 1
11 12 1
12 13 1
13 14 0
14 15 0
15 16 0
16 17 0
17 18 1
18 19 1
19 20 0
20 21 1
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

164602050
208733870
228180204
248456409
87574800
16685198
46684062
64713954
46949896
240633535
94777502
83016099
259833741
167838804
214963500
147454419
111021650
80187604
184782450
78138570
86528820
203553394
188095596
202049239
290053220
172790198
168899028
97757186
96431009
266952297
164349486
26...

result:

ok 50000 numbers

Test #3:

score: 0
Accepted
time: 65ms
memory: 9348kb

input:

50000 100000
1 2 1
2 3 0
3 4 1
4 5 0
5 6 0
6 7 1
7 8 0
8 9 0
9 10 1
10 11 1
11 12 1
12 13 1
13 14 0
14 15 1
15 16 1
16 17 1
17 18 0
18 19 0
19 20 1
20 21 1
21 22 1
22 23 0
23 24 0
24 25 1
25 26 1
26 27 0
27 28 0
28 29 1
29 30 0
30 31 1
31 32 1
32 33 1
33 34 0
34 35 1
35 36 1
36 37 1
37 38 0
38 39 0
...

output:

100196045
31414400
96903432
4429901
131353947
100466556
96621590
116427456
86564241
138309577
111227766
96757449
98894394
113624940
103437724
32090169
118889544
27383865
145395709
52415186
44958306
178247166
101837390
123750212
66411806
29005113
61920301
53700468
83473964
101048973
24035890
82224385...

result:

ok 50000 numbers

Test #4:

score: 0
Accepted
time: 77ms
memory: 9732kb

input:

50000 100000
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 0
8 9 0
9 10 0
10 11 1
11 12 0
12 13 0
13 14 1
14 15 0
15 16 1
16 17 0
17 18 0
18 19 1
19 20 0
20 21 0
21 22 0
22 23 0
23 24 1
24 25 1
25 26 0
26 27 1
27 28 1
28 29 0
29 30 0
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 0
38 39 1
...

output:

41086586
22479083
65941117
52313422
27188549
98552837
41170647
18070874
39704907
37300025
33494097
12541197
85953980
97466762
54255520
55975530
82137682
80760412
36734523
80227468
57771407
53423371
35392992
38772417
24348238
129485865
50694526
41529532
35522018
64188507
64483980
20809109
88158268
62...

result:

ok 50000 numbers

Test #5:

score: 0
Accepted
time: 108ms
memory: 9876kb

input:

50000 100000
1 2 0
2 3 0
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 0
9 10 1
10 11 1
11 12 1
12 13 0
13 14 1
14 15 0
15 16 1
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 0
29 30 1
30 31 1
31 32 0
32 33 0
33 34 1
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
...

output:

21363040
19817072
33235630
2642743
12734703
31561956
16868881
12347713
34007395
31539206
21812869
11469295
13583164
35332256
19432281
13050400
27543307
30865175
23535331
10932941
10731700
8935711
32438529
30147704
11201224
15475486
18918233
29097672
1865520
1717197
10847438
17918300
9085519
22377502...

result:

ok 50000 numbers

Test #6:

score: 0
Accepted
time: 100ms
memory: 10224kb

input:

50000 100000
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 0
7 8 1
8 9 0
9 10 1
10 11 0
11 12 1
12 13 0
13 14 1
14 15 0
15 16 1
16 17 1
17 18 0
18 19 1
19 20 1
20 21 1
21 22 0
22 23 1
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 1
30 31 1
31 32 0
32 33 0
33 34 0
34 35 1
35 36 1
36 37 1
37 38 0
38 39 1
...

output:

7034164
2604311
9210306
13276159
7323558
11457505
5477798
10888155
4546292
13775110
4723690
3315532
7247352
14850537
8847725
7929292
5197554
2059467
7544756
2500593
3970752
12419699
9568962
4563223
10626816
3277034
12260607
6928168
4303017
5299690
8738156
9317082
9746787
10042419
13632702
8481147
11...

result:

ok 50000 numbers

Test #7:

score: 0
Accepted
time: 88ms
memory: 9636kb

input:

50000 100000
1 2 1
2 3 1
3 4 1
4 5 0
5 6 0
6 7 0
7 8 1
8 9 0
9 10 0
10 11 1
11 12 1
12 13 0
13 14 1
14 15 0
15 16 1
16 17 1
17 18 0
18 19 1
19 20 0
20 21 0
21 22 0
22 23 1
23 24 1
24 25 0
25 26 1
26 27 1
27 28 0
28 29 1
29 30 1
30 31 1
31 32 0
32 33 1
33 34 1
34 35 0
35 36 1
36 37 1
37 38 1
38 39 1
...

output:

2881748
379663
1968885
883510
1429377
1317566
1691388
425238
1498644
703328
976532
252540
2157673
2046415
2184358
1823525
1052010
1808512
1132815
987060
2350191
1248681
2155738
502600
2363042
1527856
2063953
1042845
914460
1787808
1741740
1992040
730062
1592241
1369515
1084786
1140249
2712241
754218...

result:

ok 50000 numbers

Test #8:

score: 0
Accepted
time: 66ms
memory: 9640kb

input:

50000 100000
1 2 1
2 3 1
3 4 0
4 5 1
5 6 1
6 7 0
7 8 0
8 9 1
9 10 1
10 11 0
11 12 0
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 0
18 19 1
19 20 1
20 21 1
21 22 0
22 23 0
23 24 1
24 25 0
25 26 1
26 27 1
27 28 1
28 29 0
29 30 0
30 31 0
31 32 1
32 33 1
33 34 0
34 35 1
35 36 0
36 37 0
37 38 1
38 39 1
...

output:

196425
220970
672134
128953
248040
374496
332056
388195
69312
404828
506828
470044
440937
427759
304069
412812
560795
698232
549476
191135
57468
173200
255364
763568
250616
668286
251232
71252
152194
430194
671010
10672
671999
197794
308836
393499
324938
191963
182472
234993
495528
453559
86128
9629...

result:

ok 50000 numbers

Test #9:

score: 0
Accepted
time: 69ms
memory: 9352kb

input:

50000 100000
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 0
7 8 0
8 9 0
9 10 0
10 11 1
11 12 0
12 13 1
13 14 0
14 15 0
15 16 1
16 17 1
17 18 0
18 19 1
19 20 1
20 21 0
21 22 1
22 23 1
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 1
32 33 0
33 34 1
34 35 1
35 36 0
36 37 0
37 38 0
38 39 1
...

output:

468255
105020
312484
469028
46500
433476
348092
241180
416482
136152
497776
571977
530352
219162
562176
138675
705269
353652
287899
214580
13380
294272
27828
132826
749244
506820
295440
417272
370316
114926
552490
6486
834970
359255
601821
208311
337232
101539
489665
169404
93039
64173
382258
775608...

result:

ok 50000 numbers

Test #10:

score: 0
Accepted
time: 60ms
memory: 9656kb

input:

50000 100000
1 2 0
2 3 0
3 4 0
4 5 0
5 6 1
6 7 1
7 8 0
8 9 1
9 10 1
10 11 1
11 12 0
12 13 1
13 14 0
14 15 0
15 16 1
16 17 1
17 18 1
18 19 0
19 20 0
20 21 0
21 22 1
22 23 0
23 24 1
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 1
34 35 1
35 36 0
36 37 0
37 38 0
38 39 1
...

output:

663010
158597
758130
682380
443574
514836
623881
348012
155945
542531
400539
240444
166313
307926
556860
383720
97095
367865
372270
204195
787005
79165
455970
495416
156456
33165
223166
481715
416854
524138
316025
105263
274806
781025
177352
653420
491795
743770
506808
72480
505734
444805
198372
700...

result:

ok 50000 numbers

Test #11:

score: 0
Accepted
time: 27ms
memory: 8616kb

input:

50000 99998
1 2 0
1 2 1
2 3 0
2 3 1
3 4 0
3 4 1
4 5 0
4 5 1
5 6 0
5 6 1
6 7 0
6 7 1
7 8 0
7 8 1
8 9 0
8 9 1
9 10 0
9 10 1
10 11 0
10 11 1
11 12 0
11 12 1
12 13 0
12 13 1
13 14 0
13 14 1
14 15 0
14 15 1
15 16 0
15 16 1
16 17 0
16 17 1
17 18 0
17 18 1
18 19 0
18 19 1
19 20 0
19 20 1
20 21 0
20 21 1
21...

output:

357392852
286944261
25899482
106697866
266744665
188046239
246595068
282194356
149697006
36449271
55148897
105197896
112647747
361542769
153346933
426991460
799984
17749645
256444871
329993400
275444491
344593108
81998360
305443891
233695326
82148357
92148157
17449651
36449271
34349313
175796484
354...

result:

ok 50000 numbers

Test #12:

score: 0
Accepted
time: 113ms
memory: 12248kb

input:

50000 50299
1 2 0
2 3 0
3 4 0
4 5 0
5 6 0
6 7 0
7 8 0
8 9 0
9 10 0
10 11 0
11 12 0
12 13 0
13 14 0
14 15 0
15 16 0
16 17 0
17 18 0
18 19 0
19 20 0
20 21 0
21 22 0
22 23 0
23 24 0
24 25 0
25 26 0
26 27 0
27 28 0
28 29 0
29 30 0
30 31 0
31 32 0
32 33 0
33 34 0
34 35 0
35 36 0
36 37 0
37 38 0
38 39 0
3...

output:

28885380
45069427
33432760
30206043
5611707
40119773
20814082
10397200
11616787
7910426
49163370
9368174
31732491
43615079
41538187
27076798
41917819
32019460
17871476
14080806
5899035
42800174
14990686
29049896
25022003
9316314
27915136
19878279
43675167
30658188
2990993
2704160
12805154
19507614
5...

result:

ok 50000 numbers