QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#592414 | #7086. Inner Product | Afterlife | AC ✓ | 494ms | 36196kb | C++14 | 4.9kb | 2024-09-26 22:22:09 | 2024-09-26 22:22:12 |
Judging History
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"