QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#294825#5458. Shortest Path Queryushg8877TL 1639ms56920kbC++141.5kb2023-12-30 16:50:352023-12-30 16:50:35

Judging History

你现在查看的是测评时间为 2023-12-30 16:50:35 的历史记录

  • [2024-06-21 12:38:49]
  • 管理员手动重测本题所有提交记录
  • 测评结果:TL
  • 用时:1372ms
  • 内存:39564kb
  • [2023-12-30 16:50:35]
  • 评测
  • 测评结果:0
  • 用时:1639ms
  • 内存:56920kb
  • [2023-12-30 16:50:35]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5e4+5;
int n,m,q;
struct Point{
	int x,y;
	Point(int _x=0,int _y=0){x=_x,y=_y;} 
};
Point operator -(Point x,Point y){return (Point){x.x-y.x,x.y-y.y};} 
ll operator *(Point x,Point y){return x.x*y.y-x.y*y.x;} 
vector<Point> conh[MAXN];
vector<pair<int,int> > edg[MAXN];
vector<Point> solve(vector<Point> p){
	static Point st[MAXN]; static int top;
	top=0;
	sort(p.begin(),p.end(),[&](Point x,Point y){return atan2(x.x,x.y)>atan2(y.x,y.y);});
	for(Point q:p){
		while(top>=2&&(q-st[top])*(q-st[top-1])<=0) top--;
		st[++top]=q;
	}
	p.clear();
	for(int i=1;i<=top;i++) p.push_back(st[i]);
	return p;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	conh[1].push_back(Point(0,0));
	for(int i=1;i<=m;i++){
		int u,v,w;cin>>u>>v>>w;
		edg[v].push_back(MP(u,w));
	}
	for(int i=2;i<=n;i++){
		vector<Point> nds;
		for(auto e:edg[i]) for(auto p:conh[e.first])
			nds.push_back(Point(p.x+(e.second==1),p.y+(e.second==0)));
		conh[i]=solve(nds);
//		cout<<"Node "<<i<<endl;
//		for(auto p:conh[i]) cout<<p.x<<' '<<p.y<<endl;
	}
	cin>>q;
	while(q--){
		int a,b,x;cin>>b>>a>>x;
		int ans=1e9;
		auto cal=[&](int id){
			auto p=conh[x][id];
			int r=a*p.x+b*p.y;
			ans=min(ans,r);
			return r; 
		};
		int l=0,r=conh[x].size()-1,mid;
		while(l<r){
			mid=l+r>>1;
			if(cal(mid)>cal(mid+1)) l=mid+1;
			else r=mid;
		}
		cal(l);
		cout<<ans<<endl;
	}
	return 0;
}

详细

Test #1:

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

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: 191ms
memory: 17496kb

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: 580ms
memory: 30304kb

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: 940ms
memory: 39268kb

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: 1639ms
memory: 56920kb

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: 1535ms
memory: 53528kb

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: 906ms
memory: 35784kb

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: 381ms
memory: 20748kb

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: 418ms
memory: 21844kb

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: -100
Wrong Answer
time: 377ms
memory: 20460kb

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:

wrong answer 27052nd numbers differ - expected: '140122', found: '147299'