QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#646039	#21529. 动态树（简单版）	Zhou_JK	0	170ms	6088kb	C++23	3.4kb	2024-10-16 21:02:12	2024-10-16 21:02:12

Judging History

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

[2024-10-16 21:02:12]
评测

测评结果：0
用时：170ms
内存：6088kb

查看

[2024-10-16 21:02:12]
提交

answer

#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
struct LCT
{
    struct Node
    {
        int fa,ls,rs;
        int val,sum;
        int rev;
    }tree[N];
    void push_up(int u)
    {
        tree[u].sum=tree[tree[u].ls].sum^tree[tree[u].rs].sum^tree[u].val;
        return;
    }
    void reverse(int u)
    {
        swap(tree[u].ls,tree[u].rs);
        tree[u].rev^=1;
        return;
    }
    void push_down(int u)
    {
        if(!tree[u].rev) return;
        if(tree[u].ls) reverse(tree[u].ls);
        if(tree[u].rs) reverse(tree[u].rs);
        tree[u].rev=0;
        return;
    }
    int get(int u)
    {
        if(tree[tree[u].fa].ls==u) return 0;
        if(tree[tree[u].fa].rs==u) return 1;
        return -1;
    }
    bool isroot(int u)
    {
        return get(u)==-1;
    }
    void connect(int u,int v,int op)
    {
        if(u) tree[u].fa=v;
        if(v)
        {
            if(op==0) tree[v].ls=u;
            if(op==1) tree[v].rs=u;
        }
        return;
    }
    void rotate(int u)
    {
        int f=tree[u].fa,gf=tree[f].fa,r=get(u),gr=get(f);
        int v=0;
        if(r==1) v=tree[u].ls;
        if(r==0) v=tree[u].rs;
        connect(u,gf,gr);
        connect(v,f,r);
        connect(f,u,r^1);
        push_up(f);
        push_up(u);
        return;
    }
    void pushall(int u)
    {
        if(!isroot(u)) pushall(tree[u].fa);
        push_down(u);
        return;
    }
    void splay(int u)
    {
        pushall(u);
        while(!isroot(u))
        {
            int f=tree[u].fa;
            if(!isroot(f)) rotate(get(u)==get(f)?f:u);
            rotate(u);
        }
        return;
    }
    int access(int u)
    {
        int v;
        for(v=0;u;v=u,u=tree[u].fa)
        {
            splay(u);
            tree[u].rs=v;
            push_up(u);
        }
        return v;
    }
    void makeroot(int u)
    {
        access(u);
        splay(u);
        reverse(u);
        return;
    }
    int findroot(int u)
    {
        access(u);
        splay(u);
        push_down(u);
        while(tree[u].ls) u=tree[u].ls,push_down(u);
        splay(u);
        return u;
    }
    void split(int x,int y)
    {
        makeroot(x);
        access(y);
        splay(y);
        return;
    }
    bool link(int x,int y)
    {
        makeroot(x);
        if(findroot(y)==x) return false;
        tree[x].fa=y;
        return true;
    }
    bool cut(int x,int y)
    {
        if(findroot(x)!=findroot(y)) return false;
        split(x,y);
        if(tree[x].fa!=y||tree[x].rs) return false;
        tree[x].fa=tree[y].ls=0;
        push_up(y);
        return true;
    }
    int query(int x,int y)
    {
        split(x,y);
        return tree[y].sum; 
    }
    void modify(int u,int v)
    {
        splay(u);
        tree[u].val=v;
        return;
    }
}T;
int n,m;
int a[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        T.tree[i].sum=T.tree[i].val=a[i];
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==0) cout<<T.query(x,y)<<"\n";
        else if(op==1) T.link(x,y);
        else if(op==2) T.cut(x,y);
        else if(op==3) T.modify(x,y);
    }
    return 0;
}

Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Pretests

Final Tests

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 3664kb

input:

1107 4572
234284072 388981847 391448440 477366271 186930123 127662721 932242109 729840760 723502273 878156702 139426149 109192182 895711735 300412478 644823004 751154835 198812322 989657237 667888533 708218412 411100292 639169500 41236867 919203199 712987474 102870210 402909302 646634540 248335431 9...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '829684376'

Test #2:

score: 0

Wrong Answer

time: 13ms

memory: 3684kb

input:

1478 22168
569881340 405035091 712551926 875554826 406645854 501242919 392949365 237044138 991917769 860919318 602666767 824537289 108866113 139591547 894475719 715734731 605755553 104022820 783400168 675196243 810628270 544549126 785362764 761421196 242193695 758505676 432747106 153822404 399249378...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '977856141'

Test #3:

score: 0

Wrong Answer

time: 7ms

memory: 3592kb

input:

720 11779
407324044 416057248 215358620 397121163 266598227 672056288 355038763 181861594 133030450 600486797 355994904 811704323 150048063 448794624 613007406 711725050 320509098 8205562 915133242 916173863 732977813 545177862 220442466 670371541 485288754 64702329 364293219 825915255 108377643 463...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '449036533'

Test #4:

score: 0

Wrong Answer

time: 3ms

memory: 3708kb

input:

152 12209
691802886 215953826 702694628 981148343 975092377 201414321 739162800 21034610 849623247 174894124 308642547 863937500 45592629 757330862 742460999 305369753 932608714 856818299 619604710 74448671 893694992 867421355 443563472 437930232 428483966 96399062 384039387 462514529 756617956 5077...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '587046287'

Test #5:

score: 0

Wrong Answer

time: 17ms

memory: 3624kb

input:

1318 28124
943679982 599490657 14188757 119556929 88798936 61758796 922635692 247956744 77588643 228621429 202899979 544372814 419025104 50246858 364847087 231889637 901747480 923895179 122012732 194794597 617348787 758367265 874514156 205729541 236090640 244220088 523285104 684687814 548533722 3745...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '909868659'

Test #6:

score: 0

Wrong Answer

time: 8ms

memory: 5696kb

input:

1480 13659
273091642 808945296 126909509 426498595 492288255 110231631 618200926 68848092 665081898 648499844 420071326 268296562 743750189 186575204 243086966 64901921 391261005 789769656 991716058 783849739 765280282 479547496 414236979 290401751 562020126 50771452 972287665 845368884 626840962 93...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '277368671'

Test #7:

score: 0

Wrong Answer

time: 12ms

memory: 3596kb

input:

356 22139
431594498 480475890 373890370 228894305 640208283 595505266 344572785 806115258 525318212 7434316 670399747 732635286 366145994 719043994 889163353 481316643 334053518 322709687 488052698 271041133 556891981 503463278 570978111 418427570 706300514 701112253 465872167 343854348 10796679 693...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '268821729'

Test #8:

score: 0

Wrong Answer

time: 5ms

memory: 3676kb

input:

50 11882
228789343 494106370 464015946 208607989 30612082 935090584 266792064 262927962 349871422 77246250 635002760 18143685 193705091 20037444 532253744 307000673 863700107 9612369 178632626 822516422 896134450 284228663 273573982 285506358 188837597 915857315 544342920 240006709 233771383 5753795...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '544342920'

Test #9:

score: 0

Wrong Answer

time: 2ms

memory: 3660kb

input:

285 3352
582038534 874354618 806726310 653674385 772297772 295186193 603563610 369069656 585686174 161390241 223515382 798993530 34839848 597858415 632305417 284461915 396182782 530803870 966531980 290709637 319172042 322032367 551133433 955737140 820397047 398986914 822982335 590004131 622683184 21...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '158991364'

Test #10:

score: 0

Wrong Answer

time: 13ms

memory: 3648kb

input:

1166 23009
121814457 856493653 192559916 211488994 266914699 874209553 409596930 521761274 171258686 488998014 847143010 758487957 241689123 177868187 498361258 531899010 554998825 600016801 931216265 42371861 882290673 500897222 303856950 267299623 856437526 280941209 498838974 461656089 150317958 ...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '139623646'

Test #11:

score: 0

Wrong Answer

time: 116ms

memory: 3988kb

input:

12141 173689
883175862 113587309 767153473 63975437 781113122 597898346 57194917 443752894 823881866 755317463 258127039 140087455 586957338 861574464 278039976 554788225 330807907 515220000 65153632 15145921 65920285 567738421 703565961 900932465 942403662 989985109 504981988 365887866 901807269 96...

output:

result:

wrong answer 40th numbers differ - expected: '-1', found: '863721158'

Test #12:

score: 0

Wrong Answer

time: 170ms

memory: 3860kb

input:

7752 250830
597631773 176661818 485156227 625568802 597294590 597435325 857348404 817085090 592523342 8614896 28048251 874404339 485657157 744874559 357367483 825719014 146803400 302383110 309083585 192999319 546762230 544643234 678653429 996556689 849883582 508400456 948668416 371621752 382613848 1...

output:

result:

wrong answer 83rd numbers differ - expected: '-1', found: '189222390'

Test #13:

score: 0

Wrong Answer

time: 79ms

memory: 3956kb

input:

11097 120973
718385601 339533874 783190518 128303612 702689502 616478192 506735841 436109766 384473588 700034175 273821837 669150027 365238310 423587058 491529666 864149457 180078920 426454885 204104900 172286883 44243149 820224797 375205789 37076769 485913472 827308047 324202282 784645010 605128383...

output:

result:

wrong answer 14th numbers differ - expected: '-1', found: '436406070'

Test #14:

score: 0

Wrong Answer

time: 16ms

memory: 5708kb

input:

12431 43068
32882151 121154219 299411874 283222799 337460974 218845250 713830636 148790236 720001343 301205091 440770942 40757843 968133429 923228052 289604734 736186667 587661347 708981435 813775951 874625904 567310343 442698414 997073675 253786372 940362862 304346555 655143795 383344997 990964675 ...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '241525997'

Test #15:

score: 0

Wrong Answer

time: 57ms

memory: 3744kb

input:

3569 85355
340989274 973202648 19247282 372176232 424173632 284102222 245830630 76475251 210858782 148008017 411397336 319636788 743115436 301534714 718210948 378595413 108907563 232493902 73794699 941059411 454810198 266083392 313520643 505260936 551350077 898046823 922969746 326259168 864335128 98...

output:

result:

wrong answer 95th numbers differ - expected: '-1', found: '189149769'

Test #16:

score: 0

Wrong Answer

time: 135ms

memory: 3900kb

input:

8784 197628
236997472 828403196 555774219 209146695 253908918 61752823 460934705 127206200 950931157 904539626 559632554 637355378 154635658 923777011 445506141 558026378 363092290 420469819 26314289 345860659 453597653 870312681 830583024 629506845 264093034 191518281 406456617 458631008 21362144 7...

output:

result:

wrong answer 116th numbers differ - expected: '-1', found: '849930540'

Test #17:

score: 0

Wrong Answer

time: 125ms

memory: 6020kb

input:

12752 192017
732940391 996566657 646454429 744251174 63138814 179176243 284614360 952508860 453683567 308145294 446610428 622135210 87362818 430538092 168876272 217184978 660711366 578054685 287396340 33037653 390046707 68434008 534397884 708822780 949153297 380706604 402596156 453673915 280396532 1...

output:

result:

wrong answer 70th numbers differ - expected: '-1', found: '552854795'

Test #18:

score: 0

Wrong Answer

time: 100ms

memory: 5800kb

input:

7858 153287
293289490 588964112 217688247 620592747 422433255 257999041 241627372 235576742 791977172 224751651 588263307 173945591 213477227 594399068 54404444 422943469 9418343 714814000 179975901 999368692 518206286 869347173 458616660 728377002 724658548 50884538 715752571 642040443 170785705 65...

output:

result:

wrong answer 243rd numbers differ - expected: '-1', found: '1010604700'

Test #19:

score: 0

Wrong Answer

time: 91ms

memory: 3768kb

input:

4529 135866
501087624 220268341 80802717 228455303 801802052 257083126 236800464 258533444 951300442 282155790 647175433 352367278 61151871 183837977 196166101 734996913 18605037 996804531 119099272 834963735 235477918 732059314 722206859 403838549 609425799 164049011 780668781 359667773 794323212 8...

output:

result:

wrong answer 55th numbers differ - expected: '-1', found: '684409567'

Test #20:

score: 0

Wrong Answer

time: 111ms

memory: 3880kb

input:

9851 170182
633242875 976652177 677894597 46060529 207648941 397996028 499801060 808417663 957948925 568024571 224469034 664929538 245866813 510612401 80371256 215382485 745756821 499898703 887314964 45070813 482812731 51500757 45659822 555237038 76056146 46863105 685550623 839901898 449378156 95523...

output:

result:

wrong answer 115th numbers differ - expected: '-1', found: '741678330'

Test #21:

score: 0

Wrong Answer

time: 48ms

memory: 6012kb

input:

88850 169104
439219407 133382115 399964746 836979131 645620747 868404708 848737034 58938243 97319244 353759135 1215171 374936400 25992591 115486795 961065913 506783391 82698163 710319392 148676132 729664463 31992473 108553384 67398092 537908730 13852313 155118574 329404335 181982056 930216045 496154...

output:

23086497
24452222
292705663
954321424
70908517
7598320
164171537
286229315
756207570
690781632
576726629
58067731
281107857
286015148
302120160
425977867
657654000
11894210
397495630
406098237
264785863
218843949
789109377
778603391
702174204
251983494
484814430
39280804
325367975
136847969
75957303...

result:

wrong answer 1st numbers differ - expected: '-1', found: '23086497'

Test #22:

score: 0

Runtime Error

input:

100686 276212
871549739 136160440 466533606 358530650 457719179 893818276 827731972 592096685 817772116 185943697 800658414 276247893 739963945 449453970 255084909 125882444 880433752 87861892 128476988 454878151 332781894 612647844 180211299 525852359 108314585 679923461 553988700 275471409 2692542...

output:

result:

Test #23:

score: 0

Wrong Answer

time: 8ms

memory: 5596kb

input:

71770 20174
184364221 351057781 887955123 330631468 743027612 227126917 476703531 191520813 940392109 510754770 82417281 11315438 842595967 295643926 714646834 423509406 136622757 409363353 192817091 758531572 498988374 821290269 480058802 228630481 544012211 715998787 150413218 866446360 8770725 72...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '2459332'

Test #24:

score: 0

Wrong Answer

time: 81ms

memory: 6088kb

input:

87909 232192
840448446 798539162 348086368 316860154 288955927 519879240 53570589 162604471 532434703 847470642 63451649 527196736 821407946 337148398 921744942 398043127 711633512 463878886 799188433 845037842 959124918 445137886 186368588 462692408 497573685 41448214 677400774 935148558 949068213 ...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '177985468'

Test #25:

score: 0

Wrong Answer

time: 137ms

memory: 5652kb

input:

44255 241838
306372607 145838026 12744333 277579217 799007713 884285235 294354874 427411240 336661027 222390100 487638233 995501988 830486319 382941773 466029436 721504416 171216448 912534314 360374297 574640391 19876216 922985185 155197303 784807491 21513409 573064275 98966826 789945189 32147274 18...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '654659804'

Test #26:

score: 0

Time Limit Exceeded

input:

146469 105266
687560601 637165872 441062755 584116731 556695856 515380725 585339808 903253758 805470547 357493584 229359761 134463633 156065639 228688299 743405146 382576767 109098874 880362763 738419828 250624618 44896046 118841397 136431313 685391452 67276138 21915261 172678386 326150466 403210766...

output:

result:

Test #27:

score: 0

Runtime Error

input:

112953 202967
197284148 928802535 251937479 121244058 288345774 975569553 787386847 924361223 298271426 323903146 673044180 333269914 65502445 131967789 189709201 790481915 822824468 89085604 274904826 541555685 623488377 273602551 388677449 492681157 876734975 55064512 716538926 994623213 564098007...

output:

result:

Test #28:

score: 0

Wrong Answer

time: 28ms

memory: 5876kb

input:

31437 78846
86857094 881151353 593146160 278108630 406500293 686412410 205681479 179868394 172610736 499973030 543936064 747238933 483715739 180460896 268030784 455270700 694413874 463547835 347514079 692026356 346703794 786009263 534100007 934944507 599505567 340940560 261977671 369493300 211771924...

output:

result:

wrong answer 1st numbers differ - expected: '-1', found: '686417225'

Test #29:

score: 0

Runtime Error

input:

146155 19544
53461408 808048986 500213095 878164415 999654460 709393475 228471199 919424252 66896735 788719948 555663678 750644591 481969923 694955785 754663033 991994778 742698390 980213089 151399712 193051784 439140743 388837715 954068772 366730069 465171183 766271313 238952337 735839583 264773286...

output:

result:

Test #30:

score: 0

Time Limit Exceeded

input:

112696 57845
47907900 343450520 89144409 440456264 667543391 303895553 210902706 781845523 713539202 146722972 969702927 847501427 938093585 911332046 426960599 881156825 49738742 286641108 661570895 153564993 724415099 844706297 133510385 692926046 82731928 239636558 544427419 969092958 564525153 8...