QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#592414#7086. Inner ProductAfterlifeAC ✓494ms36196kbC++144.9kb2024-09-26 22:22:092024-09-26 22:22:12

Judging History

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

  • [2024-09-26 22:22:12]
  • 评测
  • 测评结果:AC
  • 用时:494ms
  • 内存:36196kb
  • [2024-09-26 22:22:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=100010;
ll W[N];
int n;
ll ans;
struct Tree2{
    vector<pair<int,int> > G[N];
    ll sw[N];
    int dfn[N],top[N],siz[N],son[N],dep[N],f[N],num;
    void dfs1(int u,int fa){
        siz[u]=1;
        son[u]=0;
        dep[u]=dep[fa]+1;
        for(auto [v,w]:G[u]){
            if(v==fa)continue;
            sw[v]=(sw[u]+w)%mod;
            f[v]=u;
            dfs1(v,u);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]){
                son[u]=v;
            }
        }
    }
    void dfs2(int u,int topf){
        dfn[u]=++num;
        top[u]=topf;
        if(!son[u])return;
        dfs2(son[u],topf);
        for(auto [v,w]:G[u]){
            if(v==f[u]||v==son[u])continue;
            dfs2(v,v);
        }
    }
    int LCA(int u,int v){
        while(top[u]^top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            u=f[top[u]];
        }
        if(dep[u]>dep[v])swap(u,v);
        return u;
    }
    ll totw;
    int totn;
    bool is[N];
    vector<pair<int,ll> > H[N];
    ll sum;
    int gn[N];
    ll gw[N];
    void dfs(int u){
        gn[u]=is[u];
        if(is[u])gw[u]=W[u];
        for(auto [v,w]:H[u]){
            dfs(v);
            gn[u]+=gn[v];
            gw[u]+=gw[v];
            sum=(sum+(gw[v]*(totn-gn[v])+gn[v]*(totw-gw[v]))%mod*w)%mod;
        }
    }
    ll calc(vector<int> a){
        totw=totn=0;
        for(auto x:a){
            ++totn;
            totw=(totw+W[x])%mod;
            is[x]=1;
        }
        sort(a.begin(),a.end(),[&](int x,int y){return dfn[x]<dfn[y];});
        vector<int> bin;
        static int st[N],top;
        st[top=1]=1;
        bin.push_back(1);
        for(auto u:a){
            if(u==1)continue;
            bin.push_back(u);
            int lca=LCA(st[top],u);
            while(dfn[st[top-1]]>=dfn[lca]){
                H[st[top-1]].emplace_back(st[top],sw[st[top]]-sw[st[top-1]]);
                --top;
            }
            if(st[top]^lca){
                bin.push_back(lca);
                H[lca].emplace_back(st[top],sw[st[top]]-sw[lca]);
                st[top]=lca;
            }
            st[++top]=u;
        }
        while(top>1){
            H[st[top-1]].emplace_back(st[top],sw[st[top]]-sw[st[top-1]]);
            --top;
        }
        sum=0;
        dfs(1);
        for(auto x:bin){
            is[x]=0;
            H[x].clear();
            gn[x]=gw[x]=0;
        }
        return sum;
    }
    void clear(int n){
        num=0;
        for(int i=1;i<=n;++i){
            G[i].clear();
        }
    }
    void adde(int u,int v,int w){
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    void init(){
        for(int i=1;i<n;++i){
            int u,v,w;
            cin>>u>>v>>w;
            adde(u,v,w);
        }
        dfs1(1,0);
        dfs2(1,1);
    }
}T2;
struct Tree1{
    vector<pair<int,int> > G[N];
    bool vis[N];
    void clear(int n){
        for(int i=1;i<=n;++i){
            G[i].clear();
            vis[i]=0;
        }
    }
    void adde(int u,int v,int w){
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    void init(){
        for(int i=1;i<n;++i){
            int u,v,w;
            cin>>u>>v>>w;
            adde(u,v,w);
        }
    }
    int siz[N],maxp[N];
    int rt;
    void get_root(int u,int fa,int total){
        siz[u]=1;
        maxp[u]=0;
        for(auto [v,w]:G[u]){
            if(v==fa||vis[v])continue;
            get_root(v,u,total);
            siz[u]+=siz[v];
            maxp[u]=max(maxp[u],siz[v]);
        }
        maxp[u]=max(maxp[u],total-siz[u]);
        if(!rt||maxp[u]<maxp[rt]){
            rt=u;
        }
    }
    vector<int> P,Q;
    void dfs1(int u,int fa,ll totw){
        W[u]=totw;
        P.push_back(u),Q.push_back(u);
        for(auto [v,w]:G[u]){
            if(v==fa||vis[v])continue;
            dfs1(v,u,(totw+w)%mod);
        }
    }
    void Div(int u){
        vis[u]=1;
        W[u]=0;
        Q.clear();
        Q.push_back(u);
        for(auto [v,w]:G[u]){
            if(vis[v])continue;
            P.clear();
            dfs1(v,u,w);
            ans=(ans-T2.calc(P))%mod;
        }
        ans=(ans+T2.calc(Q))%mod;
        for(auto [v,w]:G[u]){
            if(vis[v])continue;
            rt=0;
            get_root(v,u,siz[v]);
            Div(rt);
        }
    }
    void Solve(){
        rt=0;
        get_root(1,0,n);
        Div(rt);
    }
}T1;
void Solve(){
    cin>>n;
    ans=0;
    T1.clear(n);
    T2.clear(n);
    T1.init();
    T2.init();
    T1.Solve();
    ans=ans*2%mod;
    cout<<(ans+mod)%mod<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--)Solve();
    return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 13744kb

input:

1
2
1 2 3
1 2 4

output:

24

result:

ok "24"

Test #2:

score: 0
Accepted
time: 50ms
memory: 16748kb

input:

18265
4
1 4 770451592
2 4 277067438
3 2 307076074
3 4 164467604
1 4 588797903
2 1 537346425
1
7
7 4 382835486
2 7 473042763
5 2 39929242
6 2 585229407
3 5 807830350
1 2 898554961
3 7 541921359
2 7 796516696
6 3 239857604
4 3 145052803
5 2 418549973
1 2 781381628
9
1 7 158088424
3 7 61764661
5 1 6866...

output:

503735836
0
737031969
848125471
711293684
0
895782141
103217087
487510904
949916343
843006376
0
425493202
152334353
877947602
763745879
450239245
217817539
109645158
446460359
238672116
375432426
741349146
635549172
50862625
12408855
114291847
857285339
439093366
315692084
396448753
49849870
1573942...

result:

ok 18265 tokens

Test #3:

score: 0
Accepted
time: 47ms
memory: 15280kb

input:

20000
5
3 5 794569311
4 3 307232641
1 3 289365434
2 1 700354988
1 4 383486460
5 4 722980657
3 5 165974518
2 5 702624506
5
2 4 574855297
3 2 581682486
5 2 697270602
1 3 669374551
4 5 709221897
2 5 358274522
1 4 30427751
3 2 294939001
5
5 4 105548111
1 5 505805412
3 5 675481326
2 3 272458928
3 4 20999...

output:

379923377
157771981
78792794
902650786
796068382
39934522
97828891
258460903
67741975
518986572
617358464
279757449
767863317
926170805
173376086
984164529
165980252
224459326
660216372
789550257
99090272
531801969
414525072
219030980
746933970
526469799
940055873
91691862
244785418
161502150
503545...

result:

ok 20000 tokens

Test #4:

score: 0
Accepted
time: 61ms
memory: 15544kb

input:

10000
10
4 7 43083983
3 4 159041968
6 4 331188098
2 4 627336744
10 2 632761483
9 6 270546623
5 10 980814948
1 5 300664654
8 9 791255656
6 4 835024257
9 4 577069471
10 9 906928171
1 10 859746830
7 9 954123960
3 10 794062640
2 1 325348972
8 3 339912418
5 2 392441182
10
5 8 29444203
10 8 763643316
2 8 ...

output:

569354001
55005953
248735967
540828069
58009541
517535699
925224307
209441158
682745260
469328732
531875116
881399131
647460471
81289235
84426983
966213948
13447101
207182591
514685114
929211254
704974619
456323114
768648113
252858697
813002820
847535266
669856401
546888766
133874278
464098904
25606...

result:

ok 10000 tokens

Test #5:

score: 0
Accepted
time: 110ms
memory: 16904kb

input:

1000
100
8 74 961577785
26 8 237741238
40 8 511962199
42 26 999748991
23 26 627262064
60 23 280805048
67 23 819557610
78 23 692051345
28 78 534857058
90 26 891847856
87 28 998173732
52 28 831771820
65 23 534099123
9 87 505371795
36 23 175227975
91 90 510554725
96 52 50945098
66 91 221944214
27 96 92...

output:

584066633
677217116
955670098
529000416
277904616
644392522
369058376
475191551
320321511
118825785
93233102
323983099
676317075
701750899
148576291
792936435
333889326
645018411
832409570
737895533
913114503
936652508
148198323
764275727
8729610
33178157
227497812
594598346
811998361
665831946
3152...

result:

ok 1000 tokens

Test #6:

score: 0
Accepted
time: 111ms
memory: 17088kb

input:

1000
100
27 10 879037025
38 27 548087321
98 27 114632787
91 98 112509705
2 91 134492317
51 38 523568160
14 51 904624080
87 51 50059234
25 10 370184066
54 25 153338391
59 91 151782091
4 25 751095882
100 14 542358729
15 59 668146761
97 25 155284764
49 59 906331304
75 59 671149674
46 54 282068286
16 59...

output:

6690871
316472479
667214716
513423179
944707808
17289072
391459604
357224282
238454559
86914895
273055166
239467319
804354838
48885904
935046233
267441197
741187056
714037743
521342601
171472431
182907980
595156564
346510689
902754549
53563418
119458847
293776352
601535423
148585973
187598634
129473...

result:

ok 1000 tokens

Test #7:

score: 0
Accepted
time: 109ms
memory: 14020kb

input:

1000
100
59 62 651272073
71 59 153400700
34 62 157494863
20 62 225270418
63 59 791465674
89 34 206522760
61 63 134914742
67 62 703034420
39 63 910543779
41 89 4763519
37 20 600357747
97 67 230228456
9 67 405394142
36 20 830921727
8 63 545406961
95 89 156883691
78 95 586321546
2 37 342192357
47 41 26...

output:

883048260
102342458
49308680
848411195
792733193
905084392
882396170
804636051
39369700
952847470
313676393
36638150
11729796
868006488
631271233
110512488
384522049
76610450
499049566
18507198
988418583
966338954
906878807
50799269
73591583
155845715
943847726
871019780
188292887
153722219
42927652...

result:

ok 1000 tokens

Test #8:

score: 0
Accepted
time: 107ms
memory: 15192kb

input:

1000
100
50 64 568731313
14 50 23555295
75 50 760165451
57 14 483255323
81 64 593663224
98 64 744253168
27 14 219981212
43 50 501233797
58 98 891094979
79 64 121029863
99 79 899190298
8 27 149552517
18 79 708621044
32 27 553505205
42 79 230496454
54 18 407436078
3 42 206526123
6 43 697283724
2 6 231...

output:

841643396
608528581
846859108
781309030
813525165
549972467
660605601
326451168
975606230
16838323
960295422
283697074
561503654
761019101
707294850
503454840
712670957
904050531
174590097
796323935
763666817
179202998
140844465
460703168
813427899
935188971
113331927
939334194
20241289
22708550
576...

result:

ok 1000 tokens

Test #9:

score: 0
Accepted
time: 111ms
memory: 17200kb

input:

1000
100
11 19 486190553
14 11 333901379
68 11 657803336
81 68 890983333
42 68 100893477
80 19 281983576
56 80 305047682
12 68 564274390
38 80 726421987
77 68 677487694
79 80 52798657
33 56 773909283
40 33 571656457
25 40 716280171
8 80 770361754
92 25 508245361
62 77 826730699
22 92 757407796
4 8 4...

output:

63958840
840245701
792108221
36685385
999333493
309976575
949317316
515366846
866324907
631512551
342982958
164655907
588923605
970417539
398733305
766771424
825955104
975270706
722588084
7903488
446554216
338251244
317305112
362327987
483144819
593895033
109782751
355074927
340601246
546523899
2030...

result:

ok 1000 tokens

Test #10:

score: 0
Accepted
time: 176ms
memory: 17052kb

input:

100
1000
412 273 334195969
986 273 819701401
710 412 453711147
283 710 185643354
693 710 82511187
501 412 115391593
101 501 764309472
83 501 555206920
755 83 102795917
493 101 132890893
431 83 499461355
58 501 311712098
26 710 978854620
353 501 224027268
900 493 261335322
14 900 272550149
869 755 53...

output:

604615368
978082128
191941581
778932994
163817665
516021405
682651616
812546780
220630451
8858085
809392379
819580084
657140422
143698820
192590316
860909553
645897146
635583598
979582965
235991633
907386130
43933065
720443814
842206851
205530420
41851817
426879808
431706528
834774063
575642548
6539...

result:

ok 100 tokens

Test #11:

score: 0
Accepted
time: 176ms
memory: 14268kb

input:

100
1000
885 890 482201886
79 890 884024981
23 890 773044358
346 79 972200715
351 890 48432777
455 885 568840212
462 23 749413906
937 79 403020062
400 23 901306670
899 23 758548727
22 937 23463823
873 346 626250836
919 346 694467340
363 400 433131597
694 22 327142943
606 937 203427039
111 400 110433...

output:

679885887
942710759
708959559
809150891
978098124
816055997
929650116
17841804
554767747
980567334
746174751
394204321
649909542
820964293
998509907
908077311
17881227
692783298
220149079
368446483
486350137
16456124
304910353
544553774
340442429
217130388
950941294
824730981
981981225
475194596
539...

result:

ok 100 tokens

Test #12:

score: 0
Accepted
time: 159ms
memory: 15964kb

input:

100
1000
408 255 64740368
238 255 557257983
794 255 269482955
439 238 146037332
666 439 738683515
927 238 816958237
150 794 528503868
152 150 538660479
985 238 429734364
784 794 660040595
213 408 554697565
787 408 191242725
975 784 652185207
980 794 49007094
737 213 914900755
946 794 865865659
266 2...

output:

205022462
705720994
704979841
16070695
485906603
155609152
255004152
835650727
263569656
894760697
359967590
648954582
881602102
652042510
608362701
222001564
997842132
928810120
831657749
901780053
448866456
512147288
862285104
603485820
913798593
322382502
129221634
996392024
583634321
69213902
66...

result:

ok 100 tokens

Test #13:

score: 0
Accepted
time: 162ms
memory: 14576kb

input:

100
1000
476 659 67522093
579 659 916548859
596 579 443591974
254 476 932594693
913 579 144796594
855 913 975439560
429 596 953799790
228 596 91506324
725 659 933277820
517 659 285698428
823 596 928956929
270 579 505781463
786 228 662765222
635 823 553078719
669 254 275675672
60 635 796742549
739 57...

output:

548794585
773670400
556094471
101331604
673098988
334108796
833088355
993342957
587003404
674433917
640306486
606967103
484656058
572696808
591251243
443432991
994500028
335528737
568596932
413410253
805249805
33423124
263289623
200378545
709721884
91441586
704084591
300074351
179055921
156324304
17...

result:

ok 100 tokens

Test #14:

score: 0
Accepted
time: 289ms
memory: 16944kb

input:

10
10000
1044 2894 216102857
8040 1044 82592044
1377 2894 664093125
2844 2894 565616229
5338 1044 620675473
924 2894 906851770
8408 1044 80415921
9497 2894 627134041
8805 1044 181778077
8017 8408 372257444
7829 5338 633452355
7249 8408 767785651
7905 924 491696003
5843 8805 342303951
4986 8017 69188...

output:

384581015
610949077
224676126
361012936
780034839
301226958
834065372
809274597
218142002
662687036

result:

ok 10 tokens

Test #15:

score: 0
Accepted
time: 286ms
memory: 19572kb

input:

10
10000
4522 9928 275420975
3083 4522 31105408
1816 9928 860695294
6139 4522 432709561
196 9928 199970245
7437 3083 43610432
2747 196 502348946
8322 196 337152246
4374 2747 471414074
3478 196 108734146
2839 196 975143634
7378 6139 20875275
2772 8322 258852918
5572 6139 120345152
234 196 597484165
4...

output:

280455135
310140209
421372881
514401969
467934037
839131701
965760771
173873934
966287143
45237586

result:

ok 10 tokens

Test #16:

score: 0
Accepted
time: 267ms
memory: 19412kb

input:

10
10000
2476 3364 462283699
6998 3364 881898623
6762 6998 380561444
4853 6762 696904532
636 6762 723380285
2889 636 609007391
9193 6998 134573599
9980 636 153219675
1434 9193 194871357
7639 4853 334198036
8877 4853 151772640
2271 8877 364341100
6196 6762 402327970
3436 2889 779518490
4119 8877 9076...

output:

179473617
433465741
516920151
388146697
423691864
344009254
869456101
715139257
566600446
491200998

result:

ok 10 tokens

Test #17:

score: 0
Accepted
time: 272ms
memory: 16452kb

input:

10
10000
2619 2191 473064350
4249 2619 534471644
9393 4249 16077839
2595 4249 187998586
1380 2595 611817469
3296 2595 999902379
8247 2619 822997913
9272 4249 922711288
4737 1380 528441702
40 9393 208852864
3301 9272 836634811
280 9393 87981940
4115 8247 706521156
6334 2595 591360665
4189 2191 825226...

output:

571844100
47805019
761282754
265190312
467593533
52887292
733989742
776052354
421401084
603021227

result:

ok 10 tokens

Test #18:

score: 0
Accepted
time: 468ms
memory: 36196kb

input:

1
100000
9776 74965 843558653
34388 74965 130985194
40973 9776 611071956
61652 40973 62401333
64001 40973 685839342
38934 61652 163899259
24367 64001 776561767
1591 38934 966941186
19448 1591 57936720
8622 19448 618453827
98366 8622 915963949
21918 98366 42937455
88695 21918 729266806
18729 21918 83...

output:

723259448

result:

ok "723259448"

Test #19:

score: 0
Accepted
time: 457ms
memory: 33280kb

input:

1
100000
39951 37442 501826650
18621 39951 583699795
56855 18621 988553925
49915 56855 379041010
13280 56855 712313298
30378 13280 293504600
36849 13280 555533817
13519 36849 846254702
29614 13519 456596407
14258 29614 121575011
36257 29614 372815886
52262 36257 872696363
46602 52262 913319171
25333...

output:

19770813

result:

ok "19770813"

Test #20:

score: 0
Accepted
time: 494ms
memory: 31388kb

input:

1
100000
51447 86095 105492133
13086 86095 196763883
83257 86095 368354749
61255 51447 553490521
46464 83257 14547215
9680 83257 411470100
87807 9680 675191190
51284 9680 818381840
90275 61255 564973023
46214 46464 182810900
21701 87807 881136778
13946 87807 801791803
80837 21701 738099919
47913 902...

output:

195890164

result:

ok "195890164"

Test #21:

score: 0
Accepted
time: 478ms
memory: 32272kb

input:

1
100000
26031 63181 974591968
52447 26031 649787945
60936 63181 487118761
67232 26031 999179516
68702 26031 897514728
51756 60936 173072102
55361 60936 125748705
23511 55361 869684029
32854 23511 629867034
60048 51756 250479833
72697 32854 992108254
79235 55361 315693207
55761 72697 79625149
14487 ...

output:

355129893

result:

ok "355129893"

Test #22:

score: 0
Accepted
time: 491ms
memory: 29564kb

input:

1
100000
10017 44739 531201637
3196 44739 731348127
67871 10017 808893177
23134 44739 156197779
63238 44739 666344762
94360 3196 516251077
88302 44739 776880321
31679 44739 478586448
55736 63238 46175309
37524 63238 912037812
79226 67871 713925697
13674 55736 243900502
15241 79226 603093281
65063 15...

output:

378602247

result:

ok "378602247"

Test #23:

score: 0
Accepted
time: 492ms
memory: 30200kb

input:

1
100000
94412 18578 612883169
56375 94412 608271313
52 56375 519772018
59343 94412 531822908
98527 94412 261255414
89930 98527 959624466
40583 56375 927848791
87583 52 960593856
44709 89930 80666532
84776 52 912888086
69715 44709 916344974
27543 52 127260360
7467 52 427986155
30465 69715 348243182
...

output:

154441158

result:

ok "154441158"

Test #24:

score: 0
Accepted
time: 480ms
memory: 27936kb

input:

1
100000
90411 38622 909273478
14937 38622 195376891
45829 38622 92136818
54584 14937 570552689
15292 54584 766889842
2921 14937 988802349
17356 38622 133736732
12729 17356 311432764
96363 17356 187290640
63105 38622 570819818
31676 17356 468649069
60884 63105 502766157
69273 2921 699441496
66542 63...

output:

314603542

result:

ok "314603542"

Test #25:

score: 0
Accepted
time: 473ms
memory: 27996kb

input:

1
100000
64645 81860 424110170
37882 64645 111201817
59947 81860 682581961
70574 59947 88249916
59679 64645 864417481
98079 59947 248166664
49715 64645 363876058
68430 59947 453472939
97002 81860 250789882
44216 68430 218272281
4589 37882 443148081
81563 97002 741986697
65573 37882 9935623
37061 684...

output:

905669192

result:

ok "905669192"

Test #26:

score: 0
Accepted
time: 466ms
memory: 27516kb

input:

1
100000
35262 89269 599091498
96400 35262 323237895
77038 35262 53483770
42722 89269 581978140
54679 96400 201086940
41830 54679 141964086
18360 35262 73785124
28107 77038 974640469
90792 96400 738276380
7478 42722 368909738
84985 89269 498352768
59733 77038 477947166
504 18360 120054016
16607 9640...

output:

300286597

result:

ok "300286597"

Test #27:

score: 0
Accepted
time: 464ms
memory: 27476kb

input:

1
100000
32317 61321 840343454
21167 32317 387382605
40216 32317 591955861
20341 32317 760414456
59203 20341 559359489
55056 59203 401414774
57664 21167 6900686
4337 21167 730890976
69878 57664 808018653
39079 32317 228675968
75062 59203 623859331
74490 32317 370026580
86318 57664 414776328
10219 75...

output:

111667507

result:

ok "111667507"

Test #28:

score: 0
Accepted
time: 420ms
memory: 27620kb

input:

1
100000
85153 55422 269471078
24459 85153 159969891
27056 24459 623640188
90285 55422 163980788
59071 90285 351050124
4211 24459 675404091
40671 90285 203874333
98905 59071 684405674
3449 59071 533212203
24456 3449 88675434
26157 55422 695613609
22896 24456 476913364
16196 26157 349201913
43868 421...

output:

346455665

result:

ok "346455665"

Test #29:

score: 0
Accepted
time: 392ms
memory: 27784kb

input:

1
100000
39810 34726 69779365
10391 34726 862294824
2623 34726 810592498
73661 34726 180868266
18010 73661 175892298
65132 2623 626190649
34619 73661 581390232
49405 34619 141434587
49010 49405 194319004
54864 39810 740527787
52277 34619 372373353
64692 2623 504267605
4020 49010 326705127
43398 5227...

output:

253569479

result:

ok "253569479"

Test #30:

score: 0
Accepted
time: 138ms
memory: 17708kb

input:

100
1000
13 11 393850339
13 15 264099705
13 1 570096509
13 17 758515946
13 19 104011864
13 8 305546325
13 4 669671537
13 2 218382523
13 10 141735962
13 3 862407361
13 16 511157593
13 5 841414309
13 6 404811278
13 18 667240514
13 12 241734645
13 14 602311596
13 20 237101473
13 7 229201283
13 9 776610...

output:

843382528
46308949
431942772
720898036
653566738
494764350
791601026
597048158
498019418
479335602
695669694
324316534
155338000
339397191
49858648
42032693
150658065
718985009
124942938
221087422
172071071
432093193
716327188
424552634
261052222
225530218
277869520
135089583
471753991
820795472
519...

result:

ok 100 tokens

Test #31:

score: 0
Accepted
time: 143ms
memory: 17708kb

input:

100
1000
21 20 181263268
21 9 918700646
20 2 735967457
9 6 339639236
2 11 294780481
6 14 341037964
11 15 151216357
14 1 290323565
15 10 689126156
1 16 174862435
10 17 420216665
16 4 969385436
17 18 131169977
4 12 735699475
18 19 886784947
12 8 531525763
19 13 667521366
8 3 901242213
13 7 135524495
3...

output:

712163913
128302900
520548863
363326469
93095193
282604336
279331735
10207050
333333356
259074934
310247243
656875558
641593298
980114645
527876389
3579253
405626654
615925267
486852608
759789225
777979289
891406050
165522670
575454656
240015545
821791735
42684755
406021415
163669760
512483782
59569...

result:

ok 100 tokens

Test #32:

score: 0
Accepted
time: 144ms
memory: 15032kb

input:

100
1000
22 34 253503557
34 19 824271174
19 13 138829365
13 32 899786944
32 3 931147487
3 12 444352785
12 2 231133157
2 17 186876032
17 26 207536906
26 4 461376204
4 18 717602874
18 24 800922509
22 1 701634484
24 21 472662709
2 30 211529064
3 16 220908307
3 11 201854484
18 31 233423006
12 7 56468408...

output:

789769229
250634166
210387823
191757840
669217246
476403954
812966838
195369735
426617488
366371931
489768085
952912142
711116882
617026788
374621417
908710832
103397507
72628956
449223440
115770865
928939535
158828772
45248305
813628474
166621963
611169178
229678292
812387455
318459963
161571129
71...

result:

ok 100 tokens

Test #33:

score: 0
Accepted
time: 142ms
memory: 15304kb

input:

100
1000
5 8 179898991
8 1 264659922
5 23 123821164
23 12 913129387
8 3 736462192
3 4 209986985
4 19 700112225
19 2 779004069
4 13 288063053
1 15 786366681
19 20 309586868
12 6 492976519
12 24 379208059
1 18 841790195
24 7 194701757
6 17 591774992
18 21 418673631
21 11 963830492
21 16 675854800
24 1...

output:

625986389
828531888
432553444
133819306
881563181
519403221
967702073
970236613
921191704
194800637
259128418
860084485
787664716
511745970
658708521
713031170
425981316
286320145
194479460
120230073
8449019
780495502
810567454
521810603
140034629
208067239
644721291
171448354
591497112
861327337
83...

result:

ok 100 tokens

Test #34:

score: 0
Accepted
time: 139ms
memory: 14800kb

input:

100
1000
31 3 967093234
3 27 815010100
3 18 416944991
27 33 686809454
27 22 165405420
18 21 679043013
18 11 102002718
33 42 681248154
33 43 301523457
22 8 655510935
22 25 421099157
21 48 975683832
21 19 158614428
11 46 574592727
11 34 982926992
42 24 118555104
42 41 114747852
43 37 158219576
43 10 3...

output:

77428709
787106170
422777065
358463737
54886762
622334034
478066082
110160812
225096888
399089614
271602625
994459395
494729260
994074162
550305630
783432302
308725915
546444085
693178114
685083797
768352764
65696359
777240807
510057920
749974988
387481534
655172098
183749414
290055886
419825859
581...

result:

ok 100 tokens

Test #35:

score: 0
Accepted
time: 139ms
memory: 15148kb

input:

100
1000
1 6 482818947
1 2 978756792
6 10 550372892
2 7 619800768
10 12 995785425
7 3 340723930
12 11 750976047
3 4 617976893
11 8 208975512
4 9 595315237
8 5 807013392
3 14 585179805
14 17 948150173
17 13 577390151
14 16 773273564
13 15 595292341
2 55 952638112
29 44 536365321
44 34 372414944
34 80...

output:

58685401
749803617
319601928
894813996
651805676
319839923
464729074
950863182
914516576
318488267
574069434
629471966
84023049
304217243
794106555
586809253
942049385
360044843
92693941
207355015
322577490
723174655
702734568
788661067
674204881
976599834
896104176
202492701
254152354
850779075
119...

result:

ok 100 tokens

Test #36:

score: 0
Accepted
time: 140ms
memory: 17392kb

input:

100
1000
19 8 670986803
19 9 323115800
19 29 834647988
19 14 825318696
19 23 955058257
19 4 776965336
19 2 651039701
19 26 218691652
19 21 938242723
19 16 900741072
19 3 142594546
19 6 335756038
19 20 266456860
19 10 639152991
19 12 758394814
19 18 589196001
19 28 656725203
19 11 951239513
19 17 587...

output:

262102335
921331107
794890088
849627903
941916059
344710062
318022201
248613332
537927514
734781570
419566778
856754631
731503990
912728165
627323366
992147111
97049178
626472801
597766195
664755955
970979842
616413964
137213336
518739807
469645589
965504563
591556640
338420315
724495491
662313195
3...

result:

ok 100 tokens

Test #37:

score: 0
Accepted
time: 134ms
memory: 14340kb

input:

100
1000
692 286 487913526
692 810 354766578
692 426 238387333
692 708 385288983
692 503 304232486
692 411 883689746
692 117 953916464
692 482 314220434
692 665 508892886
692 32 809946057
692 961 568272220
692 519 401795902
692 640 966784503
692 882 576008642
692 425 401825749
692 226 517336367
692 ...

output:

744992221
897587680
284733276
293613006
555412532
867293810
636124487
613624138
92060662
814449440
466277771
210877732
21654510
444854591
432723047
780533593
458692700
663596765
320740180
133212005
532891263
696109843
98974925
727322682
322640138
245009314
578190465
978043543
131671727
845846736
723...

result:

ok 100 tokens

Test #38:

score: 0
Accepted
time: 134ms
memory: 15852kb

input:

100
1000
965 318 991209190
965 127 700265048
965 430 404837508
965 175 752115074
965 682 613423295
965 559 854008003
965 695 862772816
965 997 258204088
965 782 176798239
965 60 903672138
965 765 562983821
965 64 722593240
965 351 531553415
965 802 481236410
965 41 199297836
965 817 290434292
965 94...

output:

737606828
149571280
240832254
226279535
899281180
341972242
133488863
294259382
941540638
597737091
102437974
469697527
834985009
554183528
505401567
477195351
375029753
510525310
294509746
583929870
519828824
879255379
105499315
674343679
701719825
365514826
403364556
976647692
635442250
114864564
...

result:

ok 100 tokens

Test #39:

score: 0
Accepted
time: 120ms
memory: 14204kb

input:

100
1000
391 948 799537562
391 122 644211560
391 873 864703016
391 717 717389206
391 370 316029436
391 571 824326260
391 356 771629169
391 959 407220450
391 608 744703593
391 77 997398220
391 793 967760839
391 119 838357869
391 976 791289618
391 746 386464177
391 382 201802632
391 824 670116884
391 ...

output:

651896577
758701648
301929027
884186192
548283304
165962485
547473742
473045905
776299263
127936306
37992441
610808896
23742841
398182872
551326678
186290295
819090387
975860460
564540629
343157756
458520848
205128305
481613456
158913451
317518589
170707602
256933211
665499319
518655604
967684209
96...

result:

ok 100 tokens

Test #40:

score: 0
Accepted
time: 97ms
memory: 14596kb

input:

100
1000
267 332 491215849
267 482 383125363
267 577 336185899
267 992 184215295
267 236 625220245
267 331 188059848
267 628 475452812
267 828 146171395
267 934 207576237
267 3 191124300
267 836 267505148
332 757 259155206
482 172 962643198
577 317 585107277
992 809 899274721
236 179 648247517
331 6...

output:

975035716
802645880
443119530
847734411
365927331
801173375
724390161
336779533
523717891
564036461
485494411
479166617
137364820
135482654
390769178
289710468
754984308
465134924
179802867
559572822
622500735
532563501
436344458
948973385
291650271
826715140
44159782
433569937
761444468
14346986
23...

result:

ok 100 tokens

Test #41:

score: 0
Accepted
time: 127ms
memory: 14424kb

input:

100
1000
204 75 299544221
204 284 933656543
204 760 796051407
204 833 551041386
204 836 934411054
204 878 363410814
204 767 990893833
204 40 990155049
204 982 863864215
204 417 284850382
204 163 467249458
204 221 374919835
204 651 527412110
204 894 490335045
204 798 206812225
204 277 127930108
204 5...

output:

359611249
784274128
816759094
521059944
573445253
858022551
10391812
799712704
281935622
651759449
606978069
554882146
438142758
914335465
359255329
745578611
81766299
159738379
590717421
270919200
525008989
305315214
251619039
298371621
256910520
835937913
456203596
20436035
89775521
103911043
5507...

result:

ok 100 tokens

Test #42:

score: 0
Accepted
time: 96ms
memory: 16612kb

input:

100
1000
471 143 107872593
471 15 672570346
471 750 355916915
471 667 516315518
471 924 138569154
471 391 333729070
471 244 899750185
471 247 327554035
471 584 531769567
471 537 671991797
471 492 872026476
471 124 989132506
471 432 493732980
471 809 395562812
471 310 610868980
471 347 106060741
471 ...

output:

178230505
366016682
226192390
468195790
624723962
715222133
33959791
906620381
758933784
992114691
718940445
138827282
775440309
546963480
970706076
983228860
450565254
219167793
132993180
71571214
4929884
644027937
257209738
824490757
660256243
92423863
708935019
210092116
38668048
782293242
475204...

result:

ok 100 tokens

Test #43:

score: 0
Accepted
time: 104ms
memory: 14240kb

input:

100
1000
273 973 611168257
273 57 411484148
273 987 522367090
273 312 883141608
273 187 741175296
273 713 304047327
273 294 808606538
273 822 271537688
273 465 199674920
273 88 970750587
273 788 866738077
273 184 409929843
273 244 958501893
273 121 995757872
973 225 613373776
57 857 485743334
987 91...

output:

839081422
299445211
479166598
743877242
687375674
7736175
563633508
360689336
346342970
520048323
67352938
644609275
745696371
512726601
631177796
135965370
800891722
305576157
665697987
261082891
842403599
951568635
26675379
471782659
374832811
568374722
643890702
666196832
617598253
622608237
2392...

result:

ok 100 tokens

Test #44:

score: 0
Accepted
time: 139ms
memory: 16412kb

input:

100
1000
19 12 192603990
12 27 867045766
27 26 194033397
12 25 649729364
27 4 367004329
27 3 443338952
4 8 141974932
3 16 249400427
3 2 416262044
16 6 107978786
6 21 620856248
21 13 668864273
13 22 385662403
22 18 656339969
21 11 868422920
22 1 466838827
18 10 543017241
11 7 222290001
10 24 70835767...

output:

225344874
995060669
700662160
140011778
410579514
314640148
419019445
535550225
781409026
484347354
234396106
807285940
888892436
393516010
900422956
752592375
766847006
286694098
644419318
903690982
15965780
75205406
166077972
782962233
445777640
298023498
608970682
863052683
545377495
984985410
88...

result:

ok 100 tokens

Test #45:

score: 0
Accepted
time: 224ms
memory: 28796kb

input:

1
100000
2206 5789 937140483
5789 6666 811816889
6666 1008 875329341
1008 4447 972867751
4447 6087 408641812
6087 4075 313274692
4075 5245 160186200
5245 5285 305732381
5285 5323 626141604
5323 2003 162128316
2003 713 319637402
713 1903 136931208
1903 5506 196169616
5506 5900 364194287
5900 6717 999...

output:

591149391

result:

ok "591149391"

Test #46:

score: 0
Accepted
time: 261ms
memory: 28628kb

input:

1
100000
7523 11143 287029677
7523 10318 923629247
7523 9903 467683896
7523 501 406088194
7523 2551 220997607
7523 9472 407897367
7523 7839 265518201
7523 4057 498465691
7523 9082 127500496
7523 5735 284704430
7523 6995 682581054
7523 2508 667896999
7523 398 944208611
7523 6828 803923644
7523 10 672...

output:

35274172

result:

ok "35274172"

Test #47:

score: 0
Accepted
time: 196ms
memory: 29724kb

input:

1
100000
9289 29 227993231
9289 2253 260882438
9289 9215 909521983
9289 10156 668481193
9289 8322 284352845
9289 6804 547287946
9289 8644 902355083
9289 3534 658976655
9289 4764 231775762
9289 5689 755285759
9289 9251 809931524
9289 3377 989091489
9289 7486 301503035
9289 9152 718438952
9289 9702 59...

output:

800227329

result:

ok "800227329"

Test #48:

score: 0
Accepted
time: 298ms
memory: 28540kb

input:

1
100000
5 16 433222285
5 8 156619152
5 12 214558379
16 3 471113283
8 1 667914740
12 6 293417930
3 11 410695215
1 7 470120459
6 9 863539956
11 15 755993798
7 2 663141399
9 10 494658717
15 13 894460886
2 14 679379961
10 4 881530358
2 77 754808671
83 22 243194307
83 78 920542050
22 66 154740410
22 25 ...

output:

623800058

result:

ok "623800058"

Test #49:

score: 0
Accepted
time: 254ms
memory: 28552kb

input:

1
100000
5261 377 798779220
5261 3857 585191643
5261 3290 894065371
5261 1750 418892934
5261 5399 487140075
5261 2230 448247507
5261 1725 272803795
5261 540 481170707
5261 2131 910331248
5261 61 843298841
5261 5293 430769943
5261 738 331087046
5261 2138 258388127
5261 2411 985930296
5261 3179 193923...

output:

222598659

result:

ok "222598659"

Test #50:

score: 0
Accepted
time: 276ms
memory: 28868kb

input:

1
100000
126 145 188209730
145 146 973993378
146 98 502332445
98 142 923145373
142 124 145106416
124 149 328415086
149 40 539442275
40 108 893041058
108 109 691982913
109 136 160538209
136 72 825383310
72 125 984013870
125 88 816527671
88 102 679272486
102 118 313246905
118 152 486255048
152 139 528...

output:

264314824

result:

ok "264314824"

Test #51:

score: 0
Accepted
time: 280ms
memory: 27888kb

input:

1
100000
5380 3665 553742172
3665 5085 102552366
5085 4057 580346228
4057 134 366828313
134 273 368199626
273 1291 493787507
1291 4827 776273908
4827 1277 101257751
1277 3258 917102438
3258 2938 873228334
2938 5310 732731497
5310 1490 104674279
1490 5429 644093828
5429 5041 170615467
5041 2325 73902...

output:

709952975

result:

ok "709952975"

Test #52:

score: 0
Accepted
time: 347ms
memory: 27216kb

input:

1
100000
13242 28438 916087548
13242 31263 495090447
13242 49039 203478398
13242 82771 992504390
13242 78031 438492373
13242 58386 697532929
13242 81335 992007263
13242 69838 275567435
13242 53064 529359903
13242 91040 354167319
13242 39993 917139322
13242 88155 925814191
13242 70381 728484238
13242...

output:

578493489

result:

ok "578493489"

Test #53:

score: 0
Accepted
time: 418ms
memory: 27040kb

input:

1
100000
53028 77976 537186052
53028 90763 625853813
53028 85670 331109362
53028 68317 819034452
53028 96170 837367490
53028 25324 610863072
53028 37789 146659057
53028 62356 740688915
53028 50548 585113270
53028 79270 153422345
53028 49974 839895719
53028 44319 905692387
53028 32805 818891741
53028...

output:

883427857

result:

ok "883427857"

Test #54:

score: 0
Accepted
time: 285ms
memory: 32096kb

input:

1
100000
77852 36607 173853805
77852 48801 775800907
77852 25018 441644559
77852 76309 276299002
77852 4060 798024572
77852 6114 683786718
77852 33774 318101505
77852 91824 624335347
77852 5226 952017927
77852 49116 317611178
77852 70134 779639951
77852 68936 352425288
77852 88410 592965953
77852 54...

output:

439800141

result:

ok "439800141"

Test #55:

score: 0
Accepted
time: 249ms
memory: 35968kb

input:

1
100000
40307 48701 967799843
40307 20192 712487783
40307 52375 827916879
40307 7989 465783719
40307 84679 568665003
40307 68760 800580116
40307 23463 371173249
40307 52166 943510918
40307 62599 745411557
40307 43319 921349731
40307 16812 141265240
40307 7977 505949981
40307 60598 401685412
40307 7...

output:

753951866

result:

ok "753951866"

Test #56:

score: 0
Accepted
time: 327ms
memory: 26864kb

input:

1
100000
35587 38334 126587354
35587 50242 968128742
35587 42751 181362678
35587 68842 255060907
35587 34777 864141438
35587 68727 268488547
35587 96497 347676497
35587 87272 973103260
35587 35604 973123992
35587 88399 192672414
35587 73734 642140580
35587 46151 767419010
35587 37308 457447667
35587...

output:

721305830

result:

ok "721305830"

Test #57:

score: 0
Accepted
time: 211ms
memory: 27152kb

input:

1
100000
4032 43238 147145440
4032 29813 600158929
4032 49919 692120716
4032 36605 698698589
4032 77795 549716225
4032 58652 319940484
4032 93876 259947638
4032 32239 639162173
4032 37973 284453003
4032 29948 423618365
4032 60353 368358185
4032 84862 974915872
4032 94933 839688525
4032 54649 4459075...

output:

349615382

result:

ok "349615382"

Test #58:

score: 0
Accepted
time: 226ms
memory: 26944kb

input:

1
100000
65928 66671 143806492
65928 12603 909463421
65928 96117 643888229
65928 39068 930258304
65928 28539 459775045
65928 87987 172218780
65928 88048 305221086
65928 86766 495782015
65928 43547 361148982
65928 18729 299608500
65928 67811 194030108
65928 17691 321929382
65928 7006 430953856
65928 ...

output:

708287086

result:

ok "708287086"

Test #59:

score: 0
Accepted
time: 302ms
memory: 28796kb

input:

1
100000
3 2 441337760
3 1 432257991
2 328 144692004
156 80 650641186
80 291 419445437
80 287 645602272
291 334 292525221
334 180 795362293
180 249 615106937
249 238 905723899
238 94 934716452
94 139 737903806
139 520 385076728
139 189 144933976
520 74 489298603
189 52 250011502
74 525 449614490
52 ...

output:

449066651

result:

ok "449066651"