QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#499020	#1139. Stations	Dan4Life^#	5	50ms	4092kb	C++23	1.3kb	2024-07-30 23:20:25	2024-07-30 23:20:26

Judging History

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

[2024-07-30 23:20:26]
评测

测评结果：5
用时：50ms
内存：4092kb

查看

[2024-07-30 23:20:25]
提交

stations

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
const int mxN = 1010;
int dfs_timer = 0;
vi labels, adj[mxN];

void dfs(int s, int p){
	labels[s] = dfs_timer++;
	for(auto u : adj[s])
		if(u!=p) dfs(u,s);
	
}

vi label(int n, int k, vi u, vi v) {
	labels.clear();
	labels.resize(n,0); dfs_timer=0;
	for(int i = 0; i < n; i++) adj[i].clear();
	for(int i = 0; i < sz(u); i++){
		int a = u[i], b = v[i];
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 0; i < n; i++){
		if(sz(adj[i])==2) continue;
		dfs(i,-1); break;
	}
	//dfs(0,-1);
	return labels;
}

int find_next_station(int s, int t, vi c) {
	if(sz(c)==1) return c[0];
	for(auto u : c) if(u==t) return u;
	if(s <= c[0] and c[0] <= t) return c[0];
	if(s >= c[0] and c[0] >= t) return c[0];
	return c[1];
	
	
	if(sz(c)==1) return c[0];
	if(t>s) return c.back();
	for(auto u : c) if(u==t) return u;
	bool isRoot = (c.back()<=s);
	for(int i = 0; i < sz(c)-2+isRoot; i++)
		if(c[i] < t and t <= c[i+1]) return c[i+1];
	if(isRoot) return c[0];
	return c.back() or c[0];
	
	int sub0 = s-1-c[0];
	if(c[0]-sub0 < t and t <= c[0]) return c[0];
	return c.back();
}

源文件, 语言: C++23

詳細信息

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 28ms

memory: 3744kb

input:

output:

input:

output:

result:

ok

Test #2:

score: 5

Accepted

time: 32ms

memory: 4076kb

input:

output:

input:

output:

result:

ok

Test #3:

score: 5

Accepted

time: 50ms

memory: 3792kb

input:

output:

input:

output:

result:

ok

Test #4:

score: 5

Accepted

time: 34ms

memory: 3820kb

input:

output:

input:

output:

result:

ok

Test #5:

score: 5

Accepted

time: 36ms

memory: 3788kb

input:

output:

input:

output:

result:

ok

Test #6:

score: 5

Accepted

time: 24ms

memory: 3816kb

input:

output:

input:

output:

result:

ok

Test #7:

score: 5

Accepted

time: 32ms

memory: 3860kb

input:

output:

input:

output:

result:

ok

Test #8:

score: 5

Accepted

time: 0ms

memory: 3792kb

input:

output:

input:

output:

result:

ok

Test #9:

score: 5

Accepted

time: 0ms

memory: 3884kb

input:

output:

input:

output:

result:

ok

Test #10:

score: 5

Accepted

time: 0ms

memory: 3788kb

input:

output:

input:

output:

result:

ok

Subtask #2:

score: 0

Wrong Answer

Test #11:

score: 0

Wrong Answer

time: 32ms

memory: 3784kb

input:

output:

input:

1
50252
223 865 1
221
346 619 1
345
480 17 1
478
898 873 1
897
351 702 1
349
913 418 1
912
201 207 1
199
920 272 1
918
206 247 3
205
207
208
357 952 3
356
358
361
486 507 1
484
90 633 3
86
91
92
276 10 1
274
895 416 1
893
779 1 1
778
555 631 1
554
358 425 3
357
359
360
779 802 3
747
780
795
847 143 ...

output:

result:

wrong answer Diff at 9-th number: read 207 but expected 205

Subtask #3:

score: 0

Wrong Answer

Test #17:

score: 16

Accepted

time: 28ms

memory: 3720kb

input:

0
10
2 1000000
1 0
997 1000000
830 513
223 672
727 200
763 415
581 440
34 42
267 325
912 693
753 59
401 289
198 641
982 214
41 49
453 107
940 806
905 732
153 482
248 405
102 79
480 837
534 620
564 856
679 178
278 247
899 206
333 672
297 308
407 863
26 752
272 178
204 603
208 10
715 562
785 285
184 5...

output:

input:

output:

result:

ok

Test #18:

score: 16

Accepted

time: 32ms

memory: 3884kb

input:

0
10
999 1000000
719 816
256 855
722 661
705 575
610 707
632 426
296 99
891 512
445 475
76 601
63 756
576 934
73 186
606 363
702 69
48 768
568 128
904 82
223 805
146 382
922 467
347 433
959 614
709 998
296 4
544 64
165 989
856 470
370 230
239 810
911 976
728 952
162 752
682 305
511 782
113 37
576 41...

output:

input:

output:

result:

ok

Test #19:

score: 16

Accepted

time: 48ms

memory: 3816kb

input:

output:

input:

output:

result:

ok

Test #20:

score: 16

Accepted

time: 32ms

memory: 3792kb

input:

output:

input:

output:

result:

ok

Test #21:

score: 16

Accepted

time: 36ms

memory: 3796kb

input:

output:

input:

output:

result:

ok

Test #22:

score: 16

Accepted

time: 24ms

memory: 4076kb

input:

0
10
1000 1000000
526 757
286 227
877 883
484 370
847 13
425 107
166 745
276 357
746 21
304 131
462 834
317 58
942 423
375 631
977 908
229 838
549 167
518 60
51 772
419 970
909 386
362 829
470 46
218 986
82 787
919 307
947 691
348 900
233 650
253 762
90 850
144 627
954 103
602 268
187 746
568 992
31...

output:

input:

output:

result:

ok

Test #23:

score: 16

Accepted

time: 32ms

memory: 3808kb

input:

0
1
1000 1000000
622 589
830 829
709 500
278 363
20 230
963 181
768 29
857 332
787 757
897 285
480 939
855 617
959 84
687 755
667 30
553 1
213 98
987 780
47 851
107 764
130 863
326 832
872 636
85 159
119 330
672 210
134 576
224 282
570 387
53 941
723 69
694 642
707 49
260 390
525 768
78 273
811 220
...

output:

input:

output:

result:

ok

Test #24:

score: 16

Accepted

time: 0ms

memory: 3792kb

input:

output:

input:

output:

result:

ok

Test #25:

score: 16

Accepted

time: 0ms

memory: 3788kb

input:

output:

input:

output:

result:

ok

Test #26:

score: 16

Accepted

time: 0ms

memory: 4044kb

input:

output:

input:

output:

result:

ok

Test #27:

score: 16

Accepted

time: 36ms

memory: 4092kb

input:

output:

input:

output:

result:

ok

Test #28:

score: 0

Wrong Answer

time: 32ms

memory: 3824kb

input:

0
10
1000 1000000
802 637
810 172
802 781
109 293
802 724
488 524
73 802
802 312
108 985
802 594
305 802
802 620
382 747
841 535
802 690
987 387
269 559
201 219
982 319
228 802
802 977
291 962
657 597
69 757
321 555
825 299
802 694
363 827
802 265
475 796
600 891
802 16
802 116
487 167
150 335
175 5...

output:

input:

output:

result:

wrong answer Diff at 4-th number: read 316 but expected 314

Subtask #4:

score: 0

Wrong Answer

Test #34:

score: 10

Accepted

time: 48ms

memory: 3788kb

input:

0
10
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1

output:

input:

output:

result:

ok

Test #35:

score: 10

Accepted

time: 40ms

memory: 3744kb

input:

0
10
3 1000000000
2 1
2 0
3 1000000000
1 0
2 0
3 1000000000
2 0
0 1
3 1000000000
0 2
1 2
3 1000000000
1 2
1 0
3 1000000000
1 0
2 1
3 1000000000
0 2
1 2
3 1000000000
1 2
1 0
3 1000000000
0 2
1 0
3 1000000000
2 0
1 2

output:

input:

output:

result:

ok

Test #36:

score: 10

Accepted

time: 36ms

memory: 3796kb

input:

0
10
4 1000000000
3 1
2 0
1 0
4 1000000000
0 3
1 2
3 1
4 1000000000
3 1
0 2
0 1
4 1000000000
2 1
2 3
1 0
4 1000000000
3 1
0 1
2 3
4 1000000000
0 1
3 0
2 3
4 1000000000
2 0
3 0
1 2
4 1000000000
0 2
2 3
1 3
4 1000000000
3 2
2 1
3 0
4 1000000000
2 3
3 0
0 1

output:

input:

output:

result:

ok

Test #37:

score: 10

Accepted

time: 0ms

memory: 3812kb

input:

0
10
4 1000000000
0 1
1 2
2 3
4 1000000000
0 1
1 3
3 2
4 1000000000
0 2
2 1
1 3
4 1000000000
0 2
2 3
3 1
4 1000000000
0 3
3 1
1 2
4 1000000000
0 3
3 2
2 1
4 1000000000
1 0
0 2
2 3
4 1000000000
1 0
0 3
3 2
4 1000000000
1 2
2 0
0 3
4 1000000000
1 3
3 0
0 2

output:

input:

output:

result:

ok

Test #38:

score: 10

Accepted

time: 0ms

memory: 3872kb

input:

0
10
6 1000000000
0 1
1 2
2 3
3 4
4 5
6 1000000000
0 1
1 2
2 3
3 5
5 4
6 1000000000
0 1
1 2
2 4
4 3
3 5
6 1000000000
0 1
1 2
2 4
4 5
5 3
6 1000000000
0 1
1 2
2 5
5 3
3 4
6 1000000000
0 1
1 2
2 5
5 4
4 3
6 1000000000
0 1
1 3
3 2
2 4
4 5
6 1000000000
0 1
1 3
3 2
2 5
5 4
6 1000000000
0 1
1 3
3 4
4 2
2 ...

output:

input:

output:

result:

ok

Test #39:

score: 10

Accepted

time: 0ms

memory: 4076kb

input:

0
3
3 1000000000
0 1
1 2
3 1000000000
0 2
2 1
3 1000000000
1 0
0 2

output:

input:

output:

result:

ok

Test #40:

score: 10

Accepted

time: 36ms

memory: 3812kb

input:

0
10
4 1000000000
1 3
1 2
0 1
4 1000000000
2 3
3 0
1 3
4 1000000000
2 0
1 3
0 1
4 1000000000
1 2
3 1
1 0
4 1000000000
3 1
0 2
3 2
4 1000000000
2 0
2 1
2 3
4 1000000000
1 2
1 3
2 0
4 1000000000
0 2
2 3
2 1
4 1000000000
2 1
2 0
3 0
4 1000000000
3 0
3 2
1 0

output:

input:

output:

result:

ok

Test #41:

score: 10

Accepted

time: 40ms

memory: 3788kb

input:

0
10
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
0 1

output:

input:

output:

result:

ok

Test #42:

score: 10

Accepted

time: 40ms

memory: 4088kb

input:

0
10
3 1000000000
0 1
0 2
3 1000000000
0 1
0 2
3 1000000000
1 0
2 0
3 1000000000
1 0
0 2
3 1000000000
1 0
2 0
3 1000000000
1 0
2 0
3 1000000000
1 0
0 2
3 1000000000
1 0
2 0
3 1000000000
1 0
0 2
3 1000000000
0 1
0 2

output:

input:

output:

result:

ok

Test #43:

score: 10

Accepted

time: 36ms

memory: 3796kb

input:

0
10
4 1000000000
0 1
2 0
1 3
4 1000000000
0 1
0 2
3 1
4 1000000000
0 1
0 2
3 1
4 1000000000
0 1
0 2
1 3
4 1000000000
0 1
0 2
3 1
4 1000000000
0 1
0 2
1 3
4 1000000000
0 1
0 2
3 1
4 1000000000
0 1
0 2
3 1
4 1000000000
1 0
0 2
1 3
4 1000000000
0 1
2 0
3 1

output:

input:

output:

result:

ok

Test #44:

score: 0

Wrong Answer

time: 2ms

memory: 4072kb

input:

0
10
7 1000000000
5 3
6 3
0 3
4 3
1 3
2 3
7 1000000000
3 0
4 0
5 0
1 0
2 0
6 0
7 1000000000
4 0
2 0
3 0
6 0
1 0
5 4
7 1000000000
4 1
0 1
5 1
3 1
2 1
6 4
7 1000000000
3 1
2 1
5 1
4 1
6 1
0 3
7 1000000000
6 3
1 3
0 3
2 3
4 6
5 6
7 1000000000
5 0
4 0
3 0
2 0
6 5
1 5
7 1000000000
0 1
6 1
5 1
3 1
4 0
2 0...

output:

input:

output:

result:

wrong answer Diff at 1-th number: read 3 but expected 1

Subtask #5:

score: 0

Wrong Answer

Test #54:

score: 61

Accepted

time: 36ms

memory: 4072kb

input:

0
10
3 1000000000
1 0
2 1
998 1000000000
928 443
90 795
55 379
957 417
759 300
960 136
309 858
833 370
228 827
876 955
619 365
15 108
243 388
54 925
141 894
272 634
0 989
600 346
380 277
350 113
326 613
975 946
660 98
34 538
220 864
9 585
185 860
458 424
509 14
22 275
109 872
153 233
76 834
972 736
...

output:

input:

output:

result:

ok

Test #55:

score: 61

Accepted

time: 32ms

memory: 4076kb

input:

0
10
997 1000000000
210 799
337 790
66 160
541 810
854 650
948 726
189 923
593 566
649 647
907 215
598 271
78 173
820 920
364 470
435 553
634 846
276 104
203 761
874 954
20 983
946 834
365 933
37 641
811 497
970 551
42 389
59 52
747 45
35 291
534 616
284 677
215 83
741 600
549 680
58 500
495 489
664...

output:

input:

1
50045
648 197 2
647
649
120 84 2
119
121
429 70 2
428
430
535 259 2
534
536
776 348 2
775
777
375 158 2
374
376
279 72 2
278
280
423 507 2
422
424
752 266 2
751
753
651 126 2
650
652
297 217 2
296
298
410 404 2
409
411
835 297 2
834
836
266 99 2
265
267
757 846 2
756
758
221 961 2
220
222
123 675 ...

output:

result:

ok

Test #56:

score: 61

Accepted

time: 48ms

memory: 3872kb

input:

0
10
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
0 1
2 1000000000
0 1
2 1000000000
1 0
2 1000000000
1 0
2 1000000000
1 0

output:

input:

output:

result:

ok

Test #57:

score: 61

Accepted

time: 40ms

memory: 3788kb

input:

0
10
3 1000000000
0 2
1 0
3 1000000000
1 0
2 1
3 1000000000
2 1
0 1
3 1000000000
2 0
0 1
3 1000000000
0 1
2 1
3 1000000000
1 2
0 2
3 1000000000
0 2
2 1
3 1000000000
1 0
2 1
3 1000000000
0 2
0 1
3 1000000000
2 0
1 0

output:

input:

output:

result:

ok

Test #58:

score: 61

Accepted

time: 36ms

memory: 3812kb

input:

0
10
4 1000000000
1 2
0 2
1 3
4 1000000000
3 0
1 2
0 1
4 1000000000
2 3
3 0
0 1
4 1000000000
2 3
1 2
0 3
4 1000000000
1 3
0 3
2 0
4 1000000000
3 0
3 2
1 0
4 1000000000
3 1
0 1
2 3
4 1000000000
1 0
3 0
1 2
4 1000000000
3 1
2 3
1 0
4 1000000000
0 1
3 0
1 2

output:

input:

output:

result:

ok

Test #59:

score: 61

Accepted

time: 32ms

memory: 3812kb

input:

0
10
1000 1000000000
313 401
316 54
721 11
679 942
681 467
84 472
977 306
285 19
891 45
654 702
294 627
927 124
583 515
700 300
401 460
521 643
911 738
818 7
895 746
370 781
405 64
904 359
22 187
609 408
363 713
768 965
345 943
512 10
149 608
438 998
642 108
680 783
648 653
592 351
79 477
759 16
430...

output:

input:

output:

result:

ok

Test #60:

score: 61

Accepted

time: 32ms

memory: 3788kb

input:

0
1
1000 1000000000
165 608
217 371
579 924
67 365
865 568
258 7
999 657
669 881
268 354
140 308
76 139
428 750
616 661
178 737
179 1
705 411
437 759
119 472
353 50
549 581
327 276
319 864
662 404
619 776
651 890
153 938
580 396
501 193
560 607
786 871
291 760
898 722
511 542
743 74
742 918
431 774
...

output:

input:

output:

result:

ok

Test #61:

score: 61

Accepted

time: 0ms

memory: 3888kb

input:

0
10
4 1000000000
0 1
1 2
2 3
4 1000000000
0 1
1 3
3 2
4 1000000000
0 2
2 1
1 3
4 1000000000
0 2
2 3
3 1
4 1000000000
0 3
3 1
1 2
4 1000000000
0 3
3 2
2 1
4 1000000000
1 0
0 2
2 3
4 1000000000
1 0
0 3
3 2
4 1000000000
1 2
2 0
0 3
4 1000000000
1 3
3 0
0 2

output:

input:

output:

result:

ok

Test #62:

score: 61

Accepted

time: 0ms

memory: 3860kb

input:

0
10
6 1000000000
0 1
1 2
2 3
3 4
4 5
6 1000000000
0 1
1 2
2 3
3 5
5 4
6 1000000000
0 1
1 2
2 4
4 3
3 5
6 1000000000
0 1
1 2
2 4
4 5
5 3
6 1000000000
0 1
1 2
2 5
5 3
3 4
6 1000000000
0 1
1 2
2 5
5 4
4 3
6 1000000000
0 1
1 3
3 2
2 4
4 5
6 1000000000
0 1
1 3
3 2
2 5
5 4
6 1000000000
0 1
1 3
3 4
4 2
2 ...

output:

input:

output:

result:

ok

Test #63:

score: 61

Accepted

time: 0ms

memory: 3872kb

input:

0
3
3 1000000000
0 1
1 2
3 1000000000
0 2
2 1
3 1000000000
1 0
0 2

output:

input:

output:

result:

ok

Test #64:

score: 0

Wrong Answer

time: 32ms

memory: 4076kb

input:

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

output:

input:

output:

result:

wrong answer Diff at 1-th number: read 198 but expected 196