QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#283967	#5073. Elden Ring	C1942huangjiaxu	AC ✓	347ms	21076kb	C++14	1.3kb	2023-12-15 19:36:28	2023-12-15 19:36:29

Judging History

你现在查看的是最新测评结果

[2023-12-15 19:36:29]
评测

测评结果：AC
用时：347ms
内存：21076kb

查看

[2023-12-15 19:36:28]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n,m,A,B,l[N],c[N],d[N];
vector<int>e[N];
void solve1(){
	for(int i=2;i<=n;++i)if(l[i]>=l[1])c[i]=0;else c[i]=(A==B)?n:(l[1]-l[i]-1)/(B-A)+1;
	queue<int>q;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(auto v:e[u])if(d[v]==-1&&d[u]+1<=c[v]){
			d[v]=d[u]+1;
			q.push(v);
		}
	}
}
void solve2(){
	for(int i=2;i<=n;++i)c[i]=l[i]<l[1]?0:(l[i]-l[1])/(A-B)+1;
	priority_queue<pair<int,int> >q;
	for(auto v:e[1])if(d[v]==-1)q.push(make_pair(-c[v],v));
	for(int i=1,tt=0;!q.empty()&&i<=n;++i){
		vector<int>tmp;
		while(!q.empty()){
			int u=q.top().second;
			if(d[u]!=-1){
				q.pop();
				continue;
			}
			if(c[u]<=min(i-1,tt)){
				d[u]=i,q.pop();
				tmp.push_back(u);
			}else break;
		}
		tt+=tmp.size();
		for(auto u:tmp)
			for(auto v:e[u])if(d[v]==-1)q.push(make_pair(-c[v],v));
	}
}
void solve(){
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for(int i=1;i<=n;++i)e[i].clear(),d[i]=-(i>1);
	for(int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		e[x].push_back(y),e[y].push_back(x);
	}
	for(int i=1;i<=n;++i){
		scanf("%d",&l[i]);
		if(i>1)l[i]+=B;
	}
	if(A<=B)solve1();
	else solve2();
	printf("%d\n",d[n]);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 8380kb

input:

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

output:

2
4

result:

ok 2 number(s): "2 4"

Test #2:

score: 0

Accepted

time: 163ms

memory: 8540kb

input:

100000
6 10 107812 105568
6 5
3 6
4 6
4 2
5 1
5 6
4 5
1 3
1 2
2 5
124065 140875 29890 80077 116532 35394
9 10 82107 88302
1 2
2 3
5 3
5 1
1 4
9 6
3 5
8 2
5 6
7 5
22670 3735 33660 92823 139960 89319 83335 158330 117349
6 10 181257 173221
5 3
3 4
3 1
5 1
2 1
3 6
3 1
6 2
3 6
4 3
76902 46253 123092 2661...

output:

-1
-1
-1
1
-1
-1
-1
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
2
-1
-1
-1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
...

result:

ok 100000 numbers

Test #3:

score: 0

Accepted

time: 160ms

memory: 8456kb

input:

100000
10 10 7791 61545
9 3
3 10
7 4
2 1
3 4
2 6
8 2
2 3
5 2
3 2
142757 98694 34871 181188 28671 62924 172723 13856 11576 26661
10 10 194165 132103
2 5
8 7
3 1
7 3
1 2
6 1
4 9
1 3
4 3
10 4
176824 47360 148701 4531 66460 199228 135267 149448 65763 125940
9 10 152778 128023
3 1
3 2
1 2
1 6
5 7
5 2
4 7...

output:

-1
-1
7
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
1
-1
1
-1
-1
-1
-1
-1
-1
4
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1
1
-1
1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
1
3
-1
-1
1
1
-1
-1
-1
5
1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 100000 numbers

Test #4:

score: 0

Accepted

time: 123ms

memory: 8392kb

input:

10000
95 100 88670 88078
80 65
52 30
18 23
62 56
2 1
11 20
69 32
65 35
44 92
38 14
81 89
19 3
15 46
2 24
85 6
8 21
59 51
27 17
17 33
25 23
44 12
63 57
29 9
36 34
9 81
3 8
41 11
58 93
42 15
12 15
17 14
16 73
21 60
94 21
87 5
6 67
91 43
18 8
23 54
83 69
82 79
23 95
26 47
46 8
22 21
9 5
30 5
50 14
56 5...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 10000 numbers

Test #5:

score: 0

Accepted

time: 133ms

memory: 8324kb

input:

10000
55 100 45240 42375
2 30
41 35
44 42
20 27
25 7
43 22
14 12
25 48
2 1
48 39
22 55
28 4
13 21
2 5
27 2
18 42
18 52
34 13
50 6
6 47
6 5
37 5
35 36
31 23
12 24
1 44
9 3
9 1
7 35
26 45
44 48
27 49
40 43
34 9
43 47
26 42
49 28
53 31
11 32
8 6
22 27
23 32
6 54
1 16
22 11
34 20
21 44
31 2
9 22
23 5
1 ...

output:

-1
-1
-1
4
5
-1
6
-1
13
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
7
-1
-1
4
-1
12
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
1
18
-1
14
5
5
-1
-1
3
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
14
15
-1
-1
-1
-1
-1
-1
-...

result:

ok 10000 numbers

Test #6:

score: 0

Accepted

time: 140ms

memory: 8404kb

input:

10000
78 100 3273 35629
51 26
12 13
60 57
67 56
34 9
7 44
3 6
63 5
6 75
49 36
63 36
9 10
10 20
8 16
58 29
10 41
4 5
4 78
35 70
68 72
11 3
20 66
18 2
14 25
21 22
52 18
21 23
24 43
51 32
19 49
38 37
28 54
9 73
24 30
21 32
10 40
4 29
4 67
55 32
27 33
38 39
13 37
4 68
20 26
73 37
60 67
4 9
15 41
12 1
2 ...

output:

-1
2
-1
-1
-1
-1
-1
3
-1
-1
6
2
-1
-1
-1
-1
-1
4
-1
-1
17
-1
5
5
8
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
2
-1
-1
-1
-1
-1
-1
-1
-1
2
9
-1
-1
6
-1
-1
-1
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
3
6
5
-1
-1
3
-1
-1
-1
-1
3
3
-1
4
-1
-1
5
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
7
7
-1
-1
3
-1
-1
-1
1...

result:

ok 10000 numbers

Test #7:

score: 0

Accepted

time: 138ms

memory: 9716kb

input:

1000
765 1000 38769 38790
686 640
40 43
94 451
1 2
511 661
671 166
683 265
398 722
759 707
245 19
1 12
613 166
227 305
220 93
18 1
28 41
183 392
718 314
184 82
190 436
361 405
35 71
507 136
407 226
101 2
513 252
287 757
684 645
347 389
91 81
299 690
158 744
380 457
193 136
170 393
467 1
70 103
138 2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15
-1
-1
-1
-1
-1
11
-1
-1
16
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
8
-1
-1
3
3
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #8:

score: 0

Accepted

time: 143ms

memory: 8516kb

input:

1000
686 1000 122539 123067
518 504
263 59
629 1
539 315
122 296
182 406
347 370
4 106
143 70
70 50
298 24
373 201
84 16
44 509
241 127
562 495
54 8
198 651
207 341
625 378
185 148
468 35
279 181
95 47
581 197
338 488
44 204
572 43
362 577
340 489
561 671
20 414
526 500
496 380
300 675
564 105
647 3...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
112
-1
-1
-1
-1
-1
-1
-1
-1
-1
159
-1
-1
110
-1
-1
-1
-1
45
-1
-1
-1
-1
-1
-1
-1
16
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
80
48
7
86
-1
-1
-1
-1
-1
-1...

result:

ok 1000 numbers

Test #9:

score: 0

Accepted

time: 153ms

memory: 9696kb

input:

1000
769 1000 77850 85984
175 700
495 653
251 294
542 472
91 40
572 277
10 395
99 532
293 577
326 37
256 194
529 604
476 61
324 709
304 561
740 728
406 586
354 352
380 146
622 98
120 217
734 559
79 93
125 573
251 178
312 164
451 250
677 606
707 767
193 718
40 678
433 588
147 46
524 685
126 262
22 59...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
20
11
-1
-1
-1
15
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
21
-1
-1
-1
-1
-1
-1
-1
-1
14
-1
-1
-1
-1
-1
5
-1
-1
-1
-1
-1
21
-1
40
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
29
-1
-1
13
13
-1
-1
-1
11
25
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
71
-1
-1
-1
2
-1
-1
-1
-...

result:

ok 1000 numbers

Test #10:

score: 0

Accepted

time: 139ms

memory: 8452kb

input:

1000
537 1000 87972 185707
259 391
306 317
260 293
479 379
284 458
43 68
194 262
239 527
135 294
175 320
211 45
145 218
28 1
166 113
90 484
118 407
50 459
61 137
259 101
358 278
91 345
487 141
407 226
40 207
119 204
19 183
2 1
21 4
161 220
531 336
109 108
324 78
521 471
230 368
458 535
209 138
132 3...

output:

-1
7
-1
-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
6
-1
-1
8
-1
4
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
9
-1
-1
-1
-1
-1
-1
-1
11
5
-1
-1
-1
-1
7
-1
7
-1
5
-1
-1
-1
-1
6
4
-1
6
-1
-1
-1
11
-1
-1
-1
-1
-1
-1
6
-1
7
-1
-1
7
3
3
11
6
5
7
-1
-1
-1
-1
4
-1
-1
-1
-1
8
-1
-1
-1
-1
-1
6
-1
-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1...

result:

ok 1000 numbers

Test #11:

score: 0

Accepted

time: 153ms

memory: 10316kb

input:

100
7926 10000 63093 63190
1980 3456
155 3681
587 7801
7767 4127
4187 5514
490 6503
2265 5486
5212 2711
5786 3166
7872 5929
1000 1312
4271 3471
7342 1202
4063 6730
4556 2811
7278 3281
6235 5894
584 3136
1328 20
6103 2612
577 950
6559 5859
4539 4158
3149 3042
454 4580
1804 5691
6140 6099
3363 1432
18...

output:

-1
-1
-1
-1
-1
5
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
2282
4168
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
419
-1
-1
-1
485
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
3
-1
-1
-1
-1
-1
1273
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 100 numbers

Test #12:

score: 0

Accepted

time: 161ms

memory: 9096kb

input:

100
6857 10000 68420 69012
2703 28
2696 4445
5949 1124
6482 4800
493 315
921 5817
5452 5485
5469 2870
3584 4964
5243 5027
5592 6549
3987 2838
2408 2208
4295 2505
4292 4590
3043 6204
2686 480
5405 1630
1012 2166
6432 5467
1850 2079
598 958
2331 2992
130 1734
2253 243
439 959
1887 593
6378 5186
1244 2...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
323
-1
-1
-1
-1
-1
-1
-1
-1
56
-1
-1
-1
-1
-1
-1
26
-1
-1
-1
-1
-1
-1
-1
-1
30
-1
-1
-1
-1
-1
-1
-1
-1
116
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
124
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
172
14
-1
-1
-1
-1
-1
-1
389
-1
-1
-1
-1
-1
-1
-1
-1
-...

result:

ok 100 numbers

Test #13:

score: 0

Accepted

time: 170ms

memory: 9744kb

input:

100
8353 10000 153179 157653
188 2789
3672 1885
3775 7223
408 5334
702 6886
6767 7941
7634 5751
6437 6953
4662 3122
5355 6159
1799 945
6833 596
1953 5894
5429 2697
3587 2589
1205 5388
2475 1482
306 1453
2625 2019
5179 5325
416 2473
6823 1919
185 1711
551 2513
1075 1352
2015 3007
1661 5547
1142 1431
...

output:

-1
17
-1
-1
-1
17
-1
-1
-1
-1
-1
27
8
15
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
12
-1
-1
-1
-1
-1
16
-1
-1
-1
12
-1
-1
-1
-1
-1
13
-1
-1
-1
-1
-1
-1
-1
-1
17
-1
6
-1
-1
-1
-1
13
-1
-1
-1
-1
-1
-1
-1
-1
-1
10
20
21
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
77
-1
15
-1
-1
-1
-1
-1
24
-1
-1
-1
-1
34

result:

ok 100 numbers

Test #14:

score: 0

Accepted

time: 159ms

memory: 9084kb

input:

100
6069 10000 112617 78969
2106 5035
3943 1517
1288 10
5693 5136
905 525
5652 1065
2661 2717
846 1836
580 4265
3973 1342
5893 3265
1471 742
2150 2494
432 5731
96 605
534 3512
5589 2018
1591 701
1255 407
1645 5378
500 2486
427 5624
5739 2164
5760 1187
1723 4511
1709 5461
1441 1065
636 5295
891 4529
...

output:

8
-1
12
-1
-1
-1
6
4
12
-1
-1
-1
-1
5
-1
-1
-1
-1
-1
6
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
10
11
-1
10
-1
-1
8
-1
-1
-1
-1
8
15
-1
-1
-1
10
-1
-1
-1
10
-1
7
-1
-1
-1
7
-1
-1
-1
19
-1
-1
-1
-1
-1
6
-1
-1
-1
9
18
-1
8
-1
9
-1
-1
-1
7
-1
-1
-1
8
-1
-1
-1
-1
9
-1
-1
-1
7
-1
-1
-1
-1
23
7
9

result:

ok 100 numbers

Test #15:

score: 0

Accepted

time: 316ms

memory: 18068kb

input:

5
158995 200000 153696 153721
117979 88926
141536 92027
97977 60542
106020 56072
5835 31943
72861 48346
43307 13999
25048 11650
99687 2750
18617 35290
109969 13716
110456 42158
29866 110431
40896 79959
81031 77614
155386 102161
41309 32980
119950 145249
12492 14566
50752 99261
61527 43732
33130 8869...

output:

-1
-1
1263
-1
-1

result:

ok 5 number(s): "-1 -1 1263 -1 -1"

Test #16:

score: 0

Accepted

time: 283ms

memory: 17836kb

input:

5
162800 200000 20986 20210
4407 40416
150939 35523
130520 77709
126667 28153
71668 80108
16326 18938
10050 13123
58961 31630
24935 8802
4796 48343
4103 5016
73874 123015
109156 83937
94447 141998
12908 2946
93319 157762
74555 89835
15082 7573
113766 15131
108660 117951
57866 47839
46346 37497
54199...

output:

8
-1
-1
-1
-1

result:

ok 5 number(s): "8 -1 -1 -1 -1"

Test #17:

score: 0

Accepted

time: 347ms

memory: 19012kb

input:

5
168622 200000 151296 149635
84739 139477
42303 34850
93689 83697
1033 2094
38924 39560
155 108683
153709 52427
46680 77616
27842 78754
22461 12848
1857 89005
115080 43124
104649 129157
9787 14153
49442 108488
148731 103097
43258 95978
86323 102855
9437 45553
85495 121862
103625 57113
110516 80058
...

output:

-1
16
-1
15
-1

result:

ok 5 number(s): "-1 16 -1 15 -1"

Test #18:

score: 0

Accepted

time: 303ms

memory: 17756kb

input:

5
149776 200000 126566 56475
17108 18243
146419 13993
69520 111344
4321 57900
114456 15257
28726 7586
4175 42517
138503 40503
149333 66558
89090 29116
75015 135950
35754 91228
70791 10899
41687 27752
91975 91127
30194 23735
146095 116856
83653 110470
92582 53620
80846 137377
67115 117987
4331 90449
...

output:

-1
-1
-1
16
-1

result:

ok 5 number(s): "-1 -1 -1 16 -1"

Test #19:

score: 0

Accepted

time: 136ms

memory: 17012kb

input:

4
200000 199999 1 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

result:

ok 4 number(s): "-1 199999 199999 -1"

Test #20:

score: 0

Accepted

time: 131ms

memory: 21076kb

input:

4
200000 199999 2 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 5...

output:

result:

ok 4 number(s): "199999 -1 199997 -1"

Test #21:

score: 0

Accepted

time: 310ms

memory: 15532kb

input:

5
100000 200000 2 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 32
32 33
33 34
34 35
35 36
36 37
37 38
38 39
39 40
40 41
41 42
42 43
43 44
44 45
45 46
46 47
47 48
48 49
49 50
50 ...

output:

result:

ok 5 number(s): "99999 99999 99999 99999 99999"

Test #22:

score: 0

Accepted

time: 2ms

memory: 8384kb

input:

output:

-1

result:

ok 1 number(s): "-1"

Test #23:

score: 0

Accepted

time: 147ms

memory: 21068kb

input:

4
200000 199999 2 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 5...

output:

result:

ok 4 number(s): "199999 -1 -1 -1"