QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#140288#4609. 小 Y 和二叉树myee100 ✓503ms143924kbC++112.1kb2023-08-15 16:58:112023-08-15 16:58:13

Judging History

This is the latest submission verdict.

  • [2023-08-15 16:58:13]
  • Judged
  • Verdict: 100
  • Time: 503ms
  • Memory: 143924kb
  • [2023-08-15 16:58:11]
  • Submitted

answer

// 那就是希望。
// 即便需要取模,也是光明。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
// Heaven and Earth... My guiding star...
// Akira Complex R.I.P.
std::vector<uint>Way[1000005],V;uint W[1000005];
voi dfs(uint p,uint f)
{
    for(uint j=Way[p].size()-1;~j;j--)
        if(Way[p][j]==f)Way[p].erase(Way[p].begin()+j);else dfs(Way[p][j],p),_min(W[p],W[Way[p][j]]);
    if(Way[p].size()<2)_min(W[p],p);else if(W[Way[p][0]]>W[Way[p][1]])std::swap(Way[p][0],Way[p][1]);
}
voi dfs2(uint p)
{
    if(W[p]==p)V.push_back(p);
    if(Way[p].empty())return;
    dfs2(Way[p][0]);if(W[p]!=p)V.push_back(p);
    if(Way[p].size()==2)dfs2(Way[p][1]);
}
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n;scanf("%u",&n);
    for(uint i=0,d;i<n;i++){scanf("%u",&d),Way[i].resize(d),W[i]=-1;for(auto&s:Way[i])scanf("%u",&s),s--;}
    uint p=0;while(Way[p].size()==3)p++;
    dfs(p,-1);
    while(true)
    {
        V.push_back(p);
        if(Way[p].empty())break;
        else if(Way[p].size()==1){p=Way[p][0];if(p>W[p]){dfs2(p);break;}}
        else dfs2(Way[p][0]),p=Way[p][1];
    }
    for(uint i=0;i<n;i++)printf("%u%c",V[i]+1," \n"[i==n-1]);
    return 0;
}

// 那就是希望。
// 即便需要取模,也是光明。

詳細信息

Test #1:

score: 5
Accepted
time: 3ms
memory: 27916kb

input:

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

output:

1 2 3 5 4

result:

ok 5 number(s): "1 2 3 5 4"

Test #2:

score: 5
Accepted
time: 2ms
memory: 27604kb

input:

10
1 2
2 7 1
1 8
1 5
2 8 4
1 10
3 9 8 2
3 7 5 3
2 10 7
2 9 6

output:

1 2 3 8 4 5 7 6 10 9

result:

ok 10 numbers

Test #3:

score: 5
Accepted
time: 2ms
memory: 26684kb

input:

14
3 3 5 12
2 6 9
3 1 7 8
1 13
2 1 10
3 13 2 11
1 3
1 3
1 2
3 5 13 14
1 6
1 1
3 10 6 4
1 10

output:

2 4 13 5 7 3 8 1 12 10 14 6 11 9

result:

ok 14 numbers

Test #4:

score: 5
Accepted
time: 2ms
memory: 27620kb

input:

19
1 5
2 5 6
1 18
3 9 16 12
3 16 1 2
1 2
1 9
2 10 13
3 17 4 7
3 17 8 19
1 12
2 4 11
1 8
1 18
1 19
2 4 5
3 9 10 18
3 17 3 14
2 10 15

output:

1 2 6 5 3 18 14 17 8 13 10 15 19 9 7 4 11 12 16

result:

ok 19 numbers

Test #5:

score: 5
Accepted
time: 1ms
memory: 28436kb

input:

91
3 19 10 91
2 28 87
3 57 32 17
3 38 33 76
1 16
1 52
2 68 67
1 81
3 73 13 39
3 1 50 35
1 75
2 29 49
3 9 84 34
2 70 74
1 68
3 86 5 63
1 3
1 76
3 77 1 48
2 45 28
1 61
2 41 26
3 51 66 47
2 86 79
3 91 27 43
2 22 55
1 25
3 20 71 2
3 85 86 12
1 72
1 90
1 3
1 4
2 13 69
2 10 59
1 53
2 64 83
3 39 70 4
2 9 3...

output:

2 5 16 63 86 24 79 29 12 49 85 52 6 73 7 67 68 15 84 8 81 44 47 17 3 32 57 78 62 42 23 66 51 82 13 31 90 65 69 34 9 11 75 56 70 14 74 38 18 76 4 33 39 77 30 72 64 36 53 83 89 37 19 48 1 21 61 40 43 25 27 91 22 26 55 41 58 60 80 46 10 35 59 50 45 54 88 20 28 71 87

result:

ok 91 numbers

Test #6:

score: 5
Accepted
time: 7ms
memory: 27668kb

input:

994
2 335 143
1 351
1 307
2 811 505
2 554 529
3 226 670 252
3 418 755 915
2 309 624
2 316 871
1 994
3 721 289 315
1 270
3 312 246 464
2 697 913
3 21 892 817
1 514
1 813
1 329
2 163 272
3 674 948 374
2 568 15
1 426
1 274
1 334
2 219 882
1 285
1 352
3 889 409 958
2 461 863
2 762 478
1 318
3 302 914 98...

output:

1 2 351 116 465 518 82 822 714 825 592 635 828 770 48 988 559 4 505 587 917 811 560 99 279 783 301 676 789 678 842 498 235 741 887 58 389 231 649 968 911 141 448 900 960 293 672 118 397 150 921 86 195 535 694 539 852 184 262 147 203 456 368 248 130 255 367 946 598 330 94 645 884 212 571 687 528 31 3...

result:

ok 994 numbers

Test #7:

score: 5
Accepted
time: 0ms
memory: 28076kb

input:

1918
3 1715 675 639
1 920
2 625 1319
1 540
3 260 1572 1349
2 978 381
1 468
2 1736 433
3 1725 793 1242
1 1695
2 926 1616
1 515
2 1267 1639
2 997 386
1 96
2 1540 300
1 185
2 377 1500
2 1648 509
2 374 1916
2 130 1303
2 83 419
3 1318 1883 267
2 99 92
3 644 1015 1161
2 972 1604
3 1684 382 607
2 532 700
1...

output:

2 3 298 479 1319 625 37 735 1610 1716 123 1770 1021 355 1686 405 1402 1816 1793 192 361 717 1393 1735 1717 999 217 1198 963 1433 1656 122 409 886 1128 1613 1591 624 1561 716 877 1147 1868 712 527 238 455 1029 636 1879 684 368 619 1633 1342 113 1184 633 432 220 1785 1750 983 143 1833 1904 1453 181 15...

result:

ok 1918 numbers

Test #8:

score: 5
Accepted
time: 8ms
memory: 27376kb

input:

4894
3 1845 3084 1784
2 4305 2060
3 2055 984 578
3 2133 1179 3908
3 2191 2057 4402
2 1472 3446
2 1949 2335
2 703 1718
1 4203
2 1994 2250
1 234
2 2710 920
2 4497 2549
1 3258
1 2342
2 170 2116
1 705
2 73 2208
1 1409
1 804
1 4052
1 2391
2 1101 3687
3 423 4185 3852
1 1076
2 3228 3517
2 145 419
2 4641 46...

output:

2 6 412 3929 434 3602 1382 520 3235 1250 2785 2810 3548 1254 4614 3446 1472 115 2850 2331 1891 3873 1065 1368 3797 2783 1071 4272 41 1731 2502 4256 3302 4013 66 1790 2697 3466 4888 878 3924 4748 3111 2717 2738 2106 2614 1654 343 4749 683 1896 1242 2625 2427 4133 3966 1341 2991 3629 2031 1643 1612 94...

result:

ok 4894 numbers

Test #9:

score: 5
Accepted
time: 279ms
memory: 143924kb

input:

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

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...

result:

ok 999872 numbers

Test #10:

score: 5
Accepted
time: 39ms
memory: 41484kb

input:

99667
2 14924 10002
2 21629 32296
2 8638 1484
2 8972 13456
2 29846 25480
2 57113 39834
2 25170 22556
2 32459 46629
2 51879 49314
2 29976 23202
2 4825 13572
2 88578 70720
2 16534 13683
2 32015 11693
2 81644 78644
2 93799 11114
2 94905 24113
2 76436 77767
2 87816 8543
2 27504 21008
2 40960 43127
2 495...

output:

1 2 3 6 30 3876 9596 16556 33835 59407 82897 63353 37369 99062 71782 70209 58579 61521 59511 67995 54965 73085 76463 90851 41235 44971 13007 48769 56282 33833 35207 49819 94974 59067 45671 40937 39736 55516 38190 61915 13431 15636 33060 69644 93196 40645 56638 35174 41509 52109 55164 13574 63466 423...

result:

ok 99667 numbers

Test #11:

score: 5
Accepted
time: 141ms
memory: 61616kb

input:

299627
2 31310 4405
2 27365 31355
2 31214 295538
2 23498 20327
2 4526 272547
2 284197 271937
2 11418 19762
2 296169 12907
2 236589 241273
2 210121 227781
2 20174 15173
2 10581 320
2 28641 4411
2 24201 287615
2 279003 283387
2 24431 22452
2 286075 245800
2 298218 292885
2 291809 20702
2 18985 15005
2...

output:

1 2 11 31 71 761 8076 14858 23457 31518 21057 30680 23656 20316 10160 29856 11999 15054 19042 28654 25488 23482 15872 32156 19089 21549 21022 3615 2295 5189 12482 21871 28755 15437 2447 3237 9091 24694 2863 28378 10169 32211 30464 11581 19914 31897 23297 22133 8122 23446 15869 27959 16007 24817 1893...

result:

ok 299627 numbers

Test #12:

score: 5
Accepted
time: 503ms
memory: 137248kb

input:

991200
2 929806 924751
2 30962 22508
2 959025 966755
2 963054 11913
2 976318 8151
2 988200 989409
2 19757 987321
2 963186 965612
2 970679 958901
2 925714 966645
2 6225 5807
2 32727 27180
2 2727 19292
2 1127 4980
2 906781 908869
2 13403 949640
2 23968 990527
2 32245 19395
2 912670 910448
2 981376 981...

output:

1 2 11 47 62 613 742 1643 2289 5913 8252 18924 29227 21113 19110 26705 18694 20000 28964 25731 17554 10084 24064 3803 6372 3364 15368 30365 21794 2469 25612 25087 3696 29835 18735 4317 24501 4073 26195 22878 15330 14062 17362 16585 24198 11260 32005 31675 6758 7351 14469 22032 1758 19854 27047 11539...

result:

ok 991200 numbers

Test #13:

score: 5
Accepted
time: 36ms
memory: 30316kb

input:

99802
1 82344
3 48458 46653 40782
1 7249
3 66943 61234 85936
1 93869
1 52124
1 39647
1 75300
1 53193
1 88611
3 10987 3522 27135
3 3761 86918 94578
3 40345 85942 9297
1 54755
1 44196
1 28674
1 74148
1 78109
3 42661 49086 37289
3 48771 50498 53846
1 10512
1 81616
1 81563
3 73663 26205 83781
1 62036
1 ...

output:

1 3 7249 85406 88654 27862 33778 295 69602 77697 81768 22408 12671 95764 60513 90540 44505 11198 82250 14435 80663 28329 4744 94430 56989 75779 52874 78358 30579 399 6446 79235 48415 78773 75458 45989 51828 46053 33474 64082 44267 66805 55708 72550 72983 73376 71684 80326 81978 6834 35877 14094 5894...

result:

ok 99802 numbers

Test #14:

score: 5
Accepted
time: 364ms
memory: 67340kb

input:

990214
3 948595 18588 964516
3 976432 962104 23811
3 988059 989956 62
3 16447 21691 21195
1 31797
3 9697 8719 6693
1 972793
1 26518
3 978566 6119 28715
3 3916 13958 27891
3 851616 823411 845745
1 10219
1 981925
3 10999 31743 19567
1 17554
3 930720 927423 927992
3 897578 923006 906422
3 8444 971585 1...

output:

5 7 972793 21466 972880 31116 909 8 26518 973428 25879 30337 984971 7973 983607 976076 5806 987333 31729 2038 178 29542 1769 28505 1914 2833 977916 975494 22534 23628 974250 983626 977093 20022 1991 28055 978213 976902 21779 979889 4215 976280 22350 27509 1638 6092 972810 10749 20637 20878 976706 29...

result:

ok 990214 numbers

Test #15:

score: 5
Accepted
time: 7ms
memory: 29180kb

input:

19844
3 16878 1725 9107
2 4928 365
3 19725 6368 18492
3 1536 7723 4050
3 14014 8608 12038
3 16571 9687 5666
1 8579
1 6243
1 12821
3 1754 1970 16744
1 8502
1 14376
2 1143 12181
1 1307
3 17255 5044 16494
1 13061
1 16389
1 18782
1 13026
3 19217 17896 13428
3 10734 16786 4747
2 6084 8663
1 16445
3 17922...

output:

2 7 8579 1561 1215 17508 329 10669 6465 4055 16003 7667 8509 8219 3275 10829 8563 18653 5617 19649 12892 876 4957 3723 11403 9201 11913 10358 17158 11245 13990 6305 5698 14005 16914 4350 3540 19622 172 15431 5520 1166 7434 19401 5308 8051 13222 1459 816 7730 14019 5621 15839 10687 18695 2297 11933 2...

result:

ok 19844 numbers

Test #16:

score: 5
Accepted
time: 77ms
memory: 34568kb

input:

198297
1 173117
1 137
1 153859
1 9677
1 52522
1 154321
3 111679 146749 180703
1 102776
3 148818 16124 5112
1 51564
1 130747
1 174375
1 19107
1 169963
2 128760 183402
1 144337
1 113221
1 92536
1 47612
1 115934
2 48432 172060
2 100594 23652
1 190291
1 74767
1 32333
1 76870
1 102194
1 8712
1 184304
1 1...

output:

1 2 137 21334 189226 117052 137647 148023 118887 108579 184833 165187 110436 121942 169749 184568 8272 108200 9436 74694 188327 91416 23426 138184 38422 1521 28203 2562 157927 107130 72682 81342 61619 172075 106594 10437 156883 140083 107150 19485 158195 122215 64278 123484 47578 111813 190991 12280...

result:

ok 198297 numbers

Test #17:

score: 5
Accepted
time: 30ms
memory: 32100kb

input:

99654
2 34564 42585
2 51883 36476
2 94501 97909
2 11784 20896
3 6313 17625 74003
1 86114
3 6967 17328 17332
3 3321 76105 38882
2 27294 14951
2 28545 2833
1 63886
3 64271 92453 67538
3 52358 41635 45800
1 96600
1 6514
2 5577 5300
1 21652
1 88823
2 97400 23712
3 1155 3776 4951
3 19944 99394 92192
2 20...

output:

1 2 32917 61816 75493 78915 56063 45578 68465 49230 52303 71471 37809 83450 64414 55403 36476 66361 97159 51883 44462 10335 38082 21271 43127 44408 39006 45064 61546 49512 16727 37424 57119 11661 16915 48076 34307 25092 79310 35337 44765 45542 63892 51240 64889 34208 36076 60740 34479 40192 41063 74...

result:

ok 99654 numbers

Test #18:

score: 5
Accepted
time: 228ms
memory: 50844kb

input:

495739
3 444887 427633 460778
1 13716
3 29742 477225 462246
2 14971 22191
3 11888 11849 19739
2 24975 417136
1 4121
3 457144 490265 466653
3 422321 439036 435022
2 490856 3276
2 2177 16719
2 438170 28624
2 486850 27134
2 32638 493108
2 17472 32264
3 453602 26239 474024
2 491165 6840
1 462784
1 47461...

output:

2 4 657 13935 28654 13269 3589 7586 12328 493156 29212 11244 4384 31762 5169 14260 906 21404 24162 22337 495539 21191 22191 2551 10213 12622 14266 20361 18793 23679 28099 5999 13183 14971 449 7083 180 27811 4013 6073 494854 5909 6680 494452 7368 492746 22131 1508 5496 12305 492315 24104 32309 9319 1...

result:

ok 495739 numbers

Test #19:

score: 5
Accepted
time: 327ms
memory: 64856kb

input:

793278
3 11192 25970 772524
1 776309
2 10626 87
3 683448 671088 695128
1 739580
2 787035 27185
2 734566 734321
2 767896 772888
1 792311
2 7847 28472
3 781765 761968 756917
3 19299 726058 756517
2 29232 22929
2 764385 763243
2 754879 747451
2 766246 743195
2 7490 737133
2 8942 26011
3 787833 771010 7...

output:

2 3 31 28960 22006 32376 32690 10962 791971 1673 16184 25921 3412 17553 1266 7960 8133 25389 10522 1812 2026 4849 5921 3484 11337 30099 25293 17380 17770 22821 13143 22595 28276 13080 20418 22858 17799 17877 6093 13692 28911 7425 4183 19573 19371 21964 5175 23083 32316 12913 3143 25217 4548 19820 79...

result:

ok 793278 numbers

Test #20:

score: 5
Accepted
time: 400ms
memory: 71464kb

input:

992471
1 918297
2 14452 15800
3 7584 21650 932
2 983148 31265
3 18830 589 30635
1 990061
2 18726 965689
1 964318
1 7055
1 9888
2 965444 960074
2 31546 27302
2 990455 986741
2 986725 18714
2 969305 23951
3 27997 22829 971529
2 12906 17485
1 7151
2 943333 974178
3 989337 990082 970140
3 969172 21098 1...

output:

1 2 11349 978851 981347 15800 14452 982534 7665 979735 989416 8341 166 6826 7995 977632 987525 992385 10648 979695 8190 984452 23977 25417 23870 13857 18902 984606 981642 13101 979447 19346 983703 20151 987159 219 14202 1052 2394 15496 2463 9898 18722 985871 987789 30123 6996 25680 981462 981722 982...

result:

ok 992471 numbers

Extra Test:

score: 0
Extra Test Passed