QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334266 | #5372. 杀蚂蚁简单版 | m0NESY | 100 ✓ | 407ms | 25052kb | C++14 | 3.0kb | 2024-02-21 16:27:50 | 2024-02-21 16:27:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=998244353;
inline int powmod(int a,int b){int c=1;while(b){if(b&1)c=(ll)c*a%mod;a=(ll)a*a%mod;b>>=1;}return c;}
inline int inv(int x){return powmod(x,mod-2);}
struct E{int to,next;}edge[N<<1];
int n,q,head[N],tot,v[N],du[N],fa[N],dep[N],f[N],g[N],h[N],t[N],k[N],vis[N],st[N][20];
vector<int> vec;
void dfs(int u,int ff)
{
st[u][0]=ff;
if(u==2)g[u]=1;
if(u>2)
{
int x=fa[u],y=fa[x];
int p1=(ll)v[u]*inv(v[y]+v[u])%mod;
int p2=(ll)v[y]*inv(v[y]+v[u])%mod*f[x]%mod;
int p=(ll)p1*inv(1-p2+mod)%mod;
f[u]=p;
g[u]=(ll)g[fa[u]]*f[u]%mod;
}
if(u!=1)
{
int sum=0;
for(int i=head[u];i!=-1;i=edge[i].next)sum=(sum+v[edge[i].to])%mod;
int c=((ll)(sum-v[fa[u]]+mod)*inv(sum)%mod+(ll)v[fa[u]]*inv(sum)%mod*f[u]%mod)%mod;
h[u]=inv(1-c+mod);
t[u]=(t[ff]+(ll)h[u]*g[u]%mod)%mod;
k[u]=(k[ff]+h[u])%mod;
}
for(int i=head[u];i!=-1;i=edge[i].next)if(edge[i].to!=ff)
fa[edge[i].to]=u,dep[edge[i].to]=dep[u]+1,dfs(edge[i].to,u);
}
inline void getpath(int u,int v)
{
vec.clear();
while(u!=v)
{
if(dep[u]>dep[v])vec.push_back(u),u=fa[u];
else if(dep[u]<dep[v])vec.push_back(v),v=fa[v];
else vec.push_back(u),u=fa[u],vec.push_back(v),v=fa[v];
}
vec.push_back(u);
}
inline void paint(int u)
{
memset(vis,0,sizeof(vis));
while(u)vis[u]=1,u=fa[u];
}
inline int calc(int u)
{
if(u==1)return 1;
int v=u;
while(!vis[v])v=fa[v];
return (ll)h[u]*g[u]%mod*inv(g[v])%mod;
}
inline int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=19;i>=0;i--)if(dep[st[x][i]]>dep[y])x=st[x][i];
if(dep[x]>dep[y])x=st[x][0];
for(int i=19;i>=0;i--)if(st[x][i]&&st[x][i]!=st[y][i])x=st[x][i],y=st[y][i];
if(x!=y)x=st[x][0],y=st[y][0];
return x;
}
inline int getans(int s,int u,int v)
{
int p=lca(s,u),q=lca(s,v);
if(p==u)
{
int x=(k[q]-k[fa[u]]+mod)%mod;
int y=(t[v]-t[q]+mod)%mod;
y=(ll)y*inv(g[q])%mod;
return (x+y)%mod;
}
int y=(t[v]-t[fa[u]]+mod)%mod;
y=(ll)y*inv(g[p])%mod;
return y;
}
int main()
{
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&v[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
du[x]++;du[y]++;
edge[++tot]=(E){y,head[x]};head[x]=tot;
edge[++tot]=(E){x,head[y]};head[y]=tot;
}
dfs(1,0);
for(int j=1;j<20;j++)
for(int i=1;i<=n;i++)st[i][j]=st[st[i][j-1]][j-1];
scanf("%d",&q);
while(q--)
{
int s,u,v;
scanf("%d%d%d",&s,&u,&v);
int w=lca(u,v);
//int l=(t[u]-t[w]+mod)%mod,r=(t[v]-t[w]+mod)%mod,m=(ll)h[w]*g[w]%mod;
//printf("%d\n",((l+r)%mod+m)%mod);
int l=getans(s,w,u),r=getans(s,w,v),m=getans(s,w,w);
printf("%d\n",((l+r)%mod-m+mod)%mod);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 4224kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 4 2
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 5 3
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4320kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 3 5 1 2 5 4
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4280kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 3 2
output:
5
result:
ok single line: '5'
Test #5:
score: 0
Accepted
time: 1ms
memory: 4232kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 2 5 1 2 4 3
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4316kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 2 4
output:
6
result:
ok single line: '6'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4196kb
input:
5 1 1 1 1 1 1 2 2 3 2 4 3 5 1 2 3 5
output:
3
result:
ok single line: '3'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4228kb
input:
5 1 1 1 1 1 1 2 2 3 3 4 4 5 1 2 4 4
output:
2
result:
ok single line: '2'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #9:
score: 10
Accepted
time: 120ms
memory: 4240kb
input:
100 19082214 4807200 18093892 10128508 6278227 3082640 18435935 14945221 17570657 10054626 13020781 18926050 4884255 5459284 10075080 18518993 16590687 4103633 1887923 12545378 14553360 14115988 766212 14352785 1482486 15388118 16751947 3735054 16071111 661078 10093466 972154 5931449 18167107 109818...
output:
584487649 105375689 183540399 836906770 807065977 86021271 888605614 362898916 717572601 171877756 169742897 568399543 337164853 253104356 2092706 800994587 454522326 214671113 261859742 813312795 853226665 927653977 759323832 758339000 478192913 738386348 620107133 860692893 878764850 578900045 521...
result:
ok 100000 lines
Test #10:
score: 0
Accepted
time: 120ms
memory: 4336kb
input:
100 5779509 14152616 656474 8503627 14095555 11727974 12356084 1729896 17729842 7944694 16991545 6435274 9453104 8754271 5743490 2243680 14116156 292426 6706481 3977194 9849180 1233525 5188833 8191511 2476396 11502874 11589183 9997905 15553041 11398934 11239119 18625103 8278922 11603460 12388569 160...
output:
254821940 274461845 3366329 23616584 747463272 907982408 547436502 827855192 356423388 937507128 389384328 784087539 793295199 983416117 845557096 188357343 890990056 763323374 985092266 319747315 417667997 719892879 955729980 235139318 325589785 910034577 767275015 487744794 623437113 362000522 388...
result:
ok 100000 lines
Test #11:
score: 0
Accepted
time: 120ms
memory: 4336kb
input:
100 369779 1006956 9349847 17503913 10220636 14938645 1196297 19749049 11659785 1248372 4731829 19506662 5945083 6312396 17240491 11471094 869384 14943018 14234223 19600388 10582327 276752 6778544 4543052 7259192 14064906 9296815 19881900 12909882 15364899 3898272 8215487 1775482 13878950 1880197 19...
output:
885590350 859810213 546419053 665463385 932242241 458256389 217354939 311203856 128213507 186316281 516069217 487953875 329972875 53356533 24595074 867019881 772118045 979090003 814889925 14856253 706045800 485293200 946162740 727446250 912151961 862052232 137593129 175555537 478934634 637426584 584...
result:
ok 100000 lines
Test #12:
score: 0
Accepted
time: 120ms
memory: 4328kb
input:
100 14269305 4763951 10153534 4128997 14681370 13350972 7678806 2035272 6073698 1983526 11830927 10811443 851629 4616229 5093424 17138745 16108987 11000399 10738127 14149013 16213550 8403261 4462027 7553699 14471371 4271976 13306620 7990224 2623961 7925711 7689494 11696709 16070682 9005614 18559612 ...
output:
238919227 546470617 110117173 243195410 535688143 740799803 332584509 561109167 528357834 308131047 563457175 580343077 825634311 418130864 118830237 153792162 213724377 9326995 135506892 642632834 377526690 781036087 589856094 444234281 385790812 432719594 427508441 547234369 441263783 151801965 97...
result:
ok 100000 lines
Test #13:
score: 0
Accepted
time: 124ms
memory: 4324kb
input:
100 10770621 2561699 19351131 433146 11899836 19710011 5317695 15058625 5300154 17596612 12043166 5829738 3120363 3514071 16814312 19530594 14660022 5899846 11099513 172116 14587020 590635 10076972 9791472 18747501 9610051 19203373 16268716 13038618 11983064 6553183 12909635 13138335 12596489 940119...
output:
883480449 414786752 457907109 769747685 79170369 888770167 476171478 951103244 808266847 395739413 336331206 369625556 619712821 120929943 365933223 930443879 186691082 329433158 532233717 61003340 863677535 104025278 459276293 317252941 16401430 340673143 292275332 534407659 663598649 992587976 710...
result:
ok 100000 lines
Test #14:
score: 0
Accepted
time: 126ms
memory: 4400kb
input:
100 2643437 16727770 14160947 713726 18994986 6266026 18350691 6818112 6044848 15158147 9799251 2560223 11138435 16547487 5338010 19024010 13825652 827533 19196292 14413253 6293039 15718644 10816615 25215 15152390 8749527 11611209 7516973 170882 4665804 19624603 15502501 17554810 14938582 111986 545...
output:
426402012 331033533 308688591 144167480 127910096 113603183 257310095 976490181 300393453 733465667 618170326 231195348 870469997 894945822 585518572 970156238 150132941 373893135 719365475 466179653 750057655 906182392 804939881 659503493 481184402 173114851 675795026 156440123 821872806 506365024 ...
result:
ok 100000 lines
Test #15:
score: 0
Accepted
time: 120ms
memory: 4308kb
input:
100 18275764 1084808 15837233 1365308 10186479 15579416 18740622 2432052 14543387 3208361 6466810 7957334 11177996 9503803 4929650 11424700 10913743 12057100 9991170 14368561 15640131 18200461 19015161 9759028 5514127 8337273 11887076 16662046 14688782 16800231 17875889 9273102 6594919 9421526 31783...
output:
209263739 401620207 765229298 564507966 382601848 776545888 806915988 112864881 421441731 171809177 606349963 526190969 570640510 167742380 707537990 975636031 515893446 409532409 872708112 943124539 358632390 417044362 730861469 782170975 406977867 813799370 556456120 95434648 561691400 329191243 1...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 124ms
memory: 4328kb
input:
100 14023502 13719823 10522231 11935496 4000223 13149273 13523816 2455376 19114160 4406879 2845066 4266705 6161277 3056210 12938070 912379 9971333 11167190 3996647 952928 1360721 9957049 5249393 14915382 19506868 11714181 4664298 15558399 17192016 17332617 10590745 14090076 8733649 2826615 2761555 5...
output:
450189419 321210336 286024144 722357360 56158196 421142793 935618056 227535552 551194474 256233122 599673165 123731258 826537952 440843351 529036205 523072757 358675623 247404084 209362091 141468985 310741948 714956610 201368778 266373592 239056589 515903638 540311654 187652125 438255154 928132095 9...
result:
ok 100000 lines
Test #17:
score: 0
Accepted
time: 120ms
memory: 4204kb
input:
100 16482998 2664429 16418531 4707794 2726207 1741400 5395305 13422883 9800377 11631446 4990276 15645985 3919273 4251552 7411366 17636710 16153505 19797882 4159429 18685297 17701050 8264546 9451462 8491704 1931109 5087368 1615209 13856566 19501977 17009797 14777967 5612495 1904651 5098283 9952660 67...
output:
447758025 425108548 475058533 47409482 108752537 793842376 869635227 109712846 649916987 262966600 4487201 56542104 353092487 692096175 292719041 663615840 333720733 11185029 166602699 635961666 746709898 980364592 487166112 865452864 278379446 790060231 879073952 612567841 561028343 187874779 23800...
result:
ok 100000 lines
Subtask #3:
score: 15
Accepted
Test #18:
score: 15
Accepted
time: 305ms
memory: 24944kb
input:
100000 13643 13546 7538 2233 7731 14619 19601 8438 9556 19888 17313 1060 15168 11207 11183 16074 10758 7469 13444 9658 18326 4735 7542 13836 5863 7903 7212 14714 10416 18506 13435 14502 15271 13205 14887 18074 8353 19807 1767 19148 7343 10823 14211 66 17168 8305 1210 5436 18552 3659 886 18416 19261 ...
output:
470097670 143314895 319664187 989628182 724942465 549661815 490172883 264410099 250850293 913408788 466102803 464951422 764468729 755758546 475030770 300112112 603892921 747093262 967440122 1264162 552912646 26025219 721517270 275076549 191931901 678760307 278036996 360130747 791206265 491217660 742...
result:
ok 100000 lines
Test #19:
score: 0
Accepted
time: 304ms
memory: 24852kb
input:
100000 7573 7436 9984 2252 6052 18503 31 16126 1069 5378 10483 3727 7005 4516 13139 4506 1772 19471 3381 4672 4084 11319 3036 8162 11024 7475 7008 16380 9914 19726 799 4512 19169 14960 6795 10302 17405 6573 3559 3247 19148 15631 10915 2238 8989 17898 6403 5247 6255 12305 4333 12566 12779 11182 17064...
output:
111801098 172129117 404164713 445405216 276472705 757768805 625065364 789427663 291213940 933955541 775110966 215954655 184757237 78376608 695421289 283190271 631342927 937109577 739765699 460648915 303107688 807577336 800102713 525391747 153718591 26572469 923735199 220723292 163355255 988279059 88...
result:
ok 100000 lines
Test #20:
score: 0
Accepted
time: 304ms
memory: 24976kb
input:
100000 7754 10408 9345 12014 16443 15992 6537 3214 17391 323 17360 3642 367 4348 6479 3082 2128 19907 15285 12309 14348 12358 10994 16674 14123 10304 9148 7132 16185 18573 17272 15573 11229 12458 3445 13364 172 1680 11516 1811 16273 164 16239 16929 16243 13556 9921 16493 7834 17291 4354 16462 331 19...
output:
453210654 810215132 418290721 313259954 256178186 484117196 562026183 217562713 372439551 397578463 156005329 773019262 4766455 723539751 395254864 93762835 576298116 401452751 930578282 872399614 474214091 223925921 119168484 11686316 416040827 86207959 106041952 49651975 317893197 830123004 428069...
result:
ok 100000 lines
Test #21:
score: 0
Accepted
time: 309ms
memory: 24960kb
input:
100000 5309 19643 18246 2403 19394 3374 19270 810 5731 2719 6746 7858 4522 11464 18035 17849 13737 8718 18241 9358 17726 12389 5253 43 17897 1813 6933 11457 5515 16155 9885 15408 17007 10846 11884 5320 10150 18358 13863 53 8311 2327 5524 18581 6748 19632 8849 4262 10092 14484 1396 7569 15345 19096 1...
output:
291379624 423324059 381211587 357818197 753151608 403285526 514125565 110837486 982016513 10497186 809593540 602929523 695101256 660984576 774456420 672546793 953188130 912116121 57946539 470500688 646910891 765332835 893068487 715107060 458612470 953183724 595598373 183107766 871530489 918564839 72...
result:
ok 100000 lines
Test #22:
score: 0
Accepted
time: 300ms
memory: 24980kb
input:
100000 5920 6573 12338 4526 11199 8375 17599 4314 19387 16891 15577 17300 10001 11046 3960 18285 8728 12811 17135 3804 19867 2760 17394 19370 17810 10531 9917 5071 5487 18363 161 18383 10643 5463 7681 19010 3344 18901 16714 19826 1827 10997 7635 7708 11623 8594 15014 2954 3698 10765 19246 6601 11309...
output:
160940931 115530899 4812213 601251697 510424332 655277786 381970298 136574090 590412386 492845722 278421803 972193890 694437648 34618297 977711056 807689220 708392271 856644900 354773042 201731170 270294469 727036520 929682826 196035879 39101694 733354104 571766421 241946695 793407818 43865893 94975...
result:
ok 100000 lines
Test #23:
score: 0
Accepted
time: 305ms
memory: 24884kb
input:
100000 4401 18578 7878 14495 4073 5218 2175 18978 2402 12985 14033 12001 6673 12478 16028 13255 14770 12066 10426 9047 9161 3846 14849 19302 4403 643 2996 8300 19233 11644 9808 17096 9686 11951 3742 13490 15825 11744 15515 9241 1798 15991 2065 12960 6826 4443 19009 6589 1184 5375 4701 13679 1213 171...
output:
831301395 638594411 891344305 845448448 9361345 509822968 564544671 51030579 415307658 745760550 100009523 447213604 880450252 945462137 719106873 454306018 307211349 863869656 571463659 730442948 16376181 477449019 539554549 125186837 357704245 826429724 299705079 388829125 982386945 850381867 4430...
result:
ok 100000 lines
Test #24:
score: 0
Accepted
time: 297ms
memory: 24964kb
input:
100000 3028 15690 11382 16254 2938 7336 9596 6177 9036 19162 17581 4855 15766 8769 3534 2043 15259 17746 1803 9448 16559 18709 10207 4554 14923 17394 5012 19620 2684 19019 18213 6800 15468 5276 2707 10609 11767 7390 17631 4707 17139 8934 13498 11279 16812 11340 17021 2522 5244 13028 8630 14581 8091 ...
output:
478866071 422991010 796736479 413648210 679381958 344079455 397356290 557201528 30091321 61982037 19765593 894517618 911070007 840615368 662271300 609399613 172381143 288738429 112287414 100726790 422944817 946929844 731159609 945722883 193777668 809318854 737860540 102923633 562474521 201269058 980...
result:
ok 100000 lines
Test #25:
score: 0
Accepted
time: 317ms
memory: 24984kb
input:
100000 9703 9879 19456 19707 4708 13328 13830 7015 13934 9751 4851 16507 4857 12475 4257 2881 189 13083 16697 19889 6371 8422 2204 15333 1531 3482 12008 6061 9841 7264 11656 13703 15379 13664 12292 17424 6858 6313 9035 603 5936 1136 7035 14559 447 8094 10365 6584 6163 5227 9033 17649 18607 7244 2246...
output:
767413222 150335186 117139358 144284167 725165065 764712666 450613318 874236822 827594343 583534039 487021797 379868824 491043695 323905545 594414754 106513578 983539609 375942467 362192405 913442810 638446489 352304149 71778116 406612047 503608586 275627439 713412732 612358985 107217516 119571777 3...
result:
ok 100000 lines
Test #26:
score: 0
Accepted
time: 318ms
memory: 24892kb
input:
100000 5436 16201 10289 17004 11545 10082 777 7735 4827 16429 15251 7952 12052 5596 19390 16919 281 14309 10955 11014 9282 8699 17866 2859 11269 17217 6096 13099 12620 10169 15854 13702 15983 6401 13846 19782 8023 10045 8230 5404 225 7249 19204 17538 14407 17707 16151 8692 18740 10683 16956 6735 156...
output:
800921976 763103088 616320356 32992590 908247266 290731427 255933478 940716988 8977335 194390620 959199650 469826271 770433088 145975702 746602612 358812095 410102171 544116499 48491232 17126887 81756856 716240689 352495413 429118333 407571056 618622755 655793451 464834091 943023824 97235389 4594553...
result:
ok 100000 lines
Subtask #4:
score: 15
Accepted
Dependency #3:
100%
Accepted
Test #27:
score: 15
Accepted
time: 373ms
memory: 24888kb
input:
100000 6366 6095 19030 6124 8086 14772 14309 19146 17241 142 18854 9323 10715 7832 750 2271 19721 2209 18189 8854 6880 3105 18767 8829 10874 14605 4407 19745 567 9069 18918 16912 7413 7158 8432 4813 6416 12018 3436 19664 19454 5390 11126 10129 6287 1766 4583 340 19233 17795 12586 12602 15639 10948 1...
output:
491542341 834048168 911020189 846718723 247985804 146744133 446830322 809603158 614720860 362181212 798992665 650258366 815169260 5611237 157479827 394336241 952571222 983808128 61379754 95030699 490427313 986687150 819299773 1571850 113649834 835622771 385284072 963687801 389673758 25575110 9670387...
result:
ok 100000 lines
Test #28:
score: 0
Accepted
time: 357ms
memory: 24892kb
input:
100000 5612 18252 17263 1644 12339 12532 13871 3959 19698 6668 10061 15975 5099 17108 6494 14887 2129 1509 3647 4376 11397 11494 7638 13118 16654 15496 17642 13961 5377 10615 17222 13325 17191 9414 10769 10191 2046 6895 15497 16148 8614 16131 1519 7358 10889 15696 9124 9422 2671 16320 18128 12148 79...
output:
163872311 149586435 611437939 853062198 163948554 639025351 980367752 382569616 983656804 395812641 446863312 419842342 942060194 67495985 190725081 898202409 82337452 455984085 327714350 574201001 527102836 181532014 809658742 235155209 106674045 127091929 429819320 660381818 917610764 423200049 68...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 383ms
memory: 24856kb
input:
100000 9829 16556 2391 4411 19663 11690 8238 18583 12366 19481 3552 5103 8200 8684 16487 1102 18028 11586 1535 19304 16768 12640 1656 15394 1307 19117 16262 6784 6504 13510 10131 14388 13534 10497 4321 4878 11432 1669 13129 17720 6247 16013 15803 11520 19474 9050 5677 3257 10493 9924 6344 7916 3623 ...
output:
450348908 490657095 642662637 486204150 856319404 325476309 945167309 235206856 881983146 228880671 20713895 26029545 200417552 375897361 806445642 375800140 907351816 465915548 49967062 634841340 686382246 534068676 15657036 828377683 345276535 470694055 591773890 747635138 380328309 507461294 1582...
result:
ok 100000 lines
Test #30:
score: 0
Accepted
time: 407ms
memory: 25052kb
input:
100000 2459 3070 14770 17131 18124 12255 2990 12019 19726 16912 12824 14955 12720 4913 10568 11463 8457 11644 17893 11693 1336 14860 14972 318 10380 8207 4200 12274 19199 12053 14591 8791 18438 18803 19048 15784 13000 18246 12191 17377 6875 9239 4402 1837 18546 15004 2270 3719 17735 11296 18104 6311...
output:
24808477 789343114 360435953 85944332 302593153 305776475 311473444 384520669 543267879 128264256 811475415 330104677 104408853 755370311 629892936 614775767 879120784 865488571 547626772 533956824 663542793 862230820 69342572 222150165 386747466 581668579 88705465 627772587 239108877 249774791 2169...
result:
ok 100000 lines
Test #31:
score: 0
Accepted
time: 370ms
memory: 24976kb
input:
100000 1288 856 1142 10811 18646 8466 6253 3026 77 10727 3288 19108 7258 2347 241 19392 4042 8880 16344 148 29 17533 13180 5787 389 7835 11785 5417 8156 1518 17126 118 11459 5491 778 7894 14217 11699 3720 15250 3992 337 8482 15216 2478 18848 1022 1646 2437 18123 19399 12511 3158 17460 8096 6259 8883...
output:
264536788 761945678 233600208 649413925 883059654 479804329 17213623 558444235 743360458 962825739 60646174 373119934 341028560 89753338 226076023 225290385 24283858 391916391 397356063 26663904 406994303 811105167 128794352 274116944 749211527 53665163 679118290 819826640 191498946 940708711 655156...
result:
ok 100000 lines
Test #32:
score: 0
Accepted
time: 391ms
memory: 24984kb
input:
100000 4104 15937 8324 12901 6991 2169 18947 15038 9497 4385 2190 19615 9781 5662 16601 12317 11059 5168 8532 13481 10026 1538 2566 13509 11684 18186 558 11660 4498 15045 12630 17799 5473 13348 5506 17663 15760 15351 19878 3837 9315 3275 2658 16472 4368 18167 4095 9327 5189 5832 12871 702 749 7648 1...
output:
426002391 467367606 169895868 568038732 81024164 650471116 889612967 657220152 794936265 843611730 295308573 780284900 633390759 713397083 72883478 30967725 102875298 282634457 971137384 698595869 6281992 143355298 530322576 492761974 540568737 738601151 2306139 94989299 180876113 826446641 58761949...
result:
ok 100000 lines
Test #33:
score: 0
Accepted
time: 372ms
memory: 24892kb
input:
100000 10859 8772 18575 10700 17776 19957 1217 5792 5370 9841 1162 5389 14266 6917 6396 11280 15382 6971 3458 4146 15153 6723 9811 3779 3295 9990 3864 19286 9678 12917 11488 5506 15935 12865 3018 14696 17555 4474 10512 13879 1020 17664 18998 12373 3374 16647 14314 3633 6263 10461 16835 19288 9710 13...
output:
822231450 197793040 898281084 32611025 162470818 40754344 105243787 767198772 437492776 457236330 912877601 75272807 842417421 82035926 227684572 19624317 881052573 272479132 94814452 252986696 442005304 57503811 526921774 324743212 770498209 608542508 88245071 82924470 311591823 185552943 42719141 ...
result:
ok 100000 lines
Test #34:
score: 0
Accepted
time: 370ms
memory: 25048kb
input:
100000 14989 2660 13319 16359 5473 14444 1234 2105 11424 18847 18659 18175 11365 19647 12316 13689 15366 4016 18006 319 19268 17298 10323 15218 13671 12537 13160 11024 1320 11160 3093 10580 16772 4944 8107 17334 5613 11031 13355 13509 985 18534 9647 19093 19816 19165 14490 4020 17932 1346 19679 1820...
output:
344819264 653589418 131850697 121149949 986578905 603047358 892820281 487008922 506970100 486978567 100164524 747717612 599455252 224950171 759731478 177408447 342546825 972031017 132729173 523430173 985930925 15646956 479625847 132087297 808701362 209877323 364316937 309106493 271587618 126830067 4...
result:
ok 100000 lines
Test #35:
score: 0
Accepted
time: 394ms
memory: 24884kb
input:
100000 1484 8390 15753 598 14593 16508 19826 12233 17078 1174 8808 13974 11479 2896 9710 6509 4838 19095 520 13555 16966 4345 15508 3138 2109 6463 13703 11271 6632 57 18944 13331 9438 5839 17035 2480 3965 5483 1001 8974 924 11374 9065 15877 15207 16265 4486 16961 3410 5987 4424 3874 18702 2262 14595...
output:
765352133 890791405 24629397 253259050 14407808 815669264 311637572 460003479 37990519 962985951 567328615 670529260 300191285 908222831 135022049 32600342 190690070 963189283 86345839 249361294 205253218 994864229 721528780 287638008 614613941 502830444 302815289 200307800 362823144 968967818 68977...
result:
ok 100000 lines
Subtask #5:
score: 20
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #36:
score: 20
Accepted
time: 262ms
memory: 17800kb
input:
100000 16755 12842 15257 1470 11658 18433 1786 3302 11140 5288 6429 13445 13668 5002 1832 4875 13390 10943 3831 14268 17844 7252 15605 15856 217 13029 16922 3749 3472 5701 8955 10152 11697 12412 7209 13405 15247 11317 15120 9907 1691 17013 17163 10699 17455 3686 11545 19260 14676 2729 18819 13773 67...
output:
840762489 613417011 179538462 952464613 4867889 383298276 765711449 778343499 24874245 741189587 140915474 799013195 685157695 200169762 568468540 303056373 475691821 787189709 68838435 992527578 92799592 639368358 152358186 78961318 583467014 41867191 399334246 229617394 157462671 976605763 3808929...
result:
ok 100000 lines
Test #37:
score: 0
Accepted
time: 250ms
memory: 18380kb
input:
100000 7351 4945 1450 11884 8835 648 3443 15731 9009 2127 19358 3483 4623 17424 3606 5483 16253 9256 19653 16461 17034 15866 3777 14707 15910 11779 13350 4842 11405 15787 10681 1309 16141 4573 7557 15220 8222 11291 15792 9004 15080 6911 16139 19612 11920 12302 19193 5486 14721 10171 16822 5750 18470...
output:
793329480 25691406 135711465 515878373 907470066 836372343 645115826 747597850 630981390 506008075 725772389 489628752 969372761 246335446 554201699 785658777 826099582 497939464 398371136 826776308 940114110 983799903 260543173 9233844 826995257 836423360 77615168 377582284 234014652 882972001 4454...
result:
ok 100000 lines
Test #38:
score: 0
Accepted
time: 269ms
memory: 19188kb
input:
100000 12113 881 16412 7919 18498 7820 3241 15755 2275 18968 8167 6023 14226 17202 10199 10318 7787 308 8206 14308 13991 9521 16525 14409 12720 12301 15524 18917 6306 12992 7401 12944 15420 18632 17901 19202 5390 13095 10940 1486 17087 5625 9389 1562 16986 9543 5787 2180 3379 15584 1038 4109 16819 1...
output:
997457796 762202574 974995469 307226109 630429953 531196303 216156017 249644111 836124836 829537649 214780608 321200762 356211315 826815360 402217454 735046589 265469071 537533218 18405883 277620088 209704571 65572758 944946551 317385551 585199737 354952107 597764487 278252047 124189416 811480429 56...
result:
ok 100000 lines
Test #39:
score: 0
Accepted
time: 262ms
memory: 19840kb
input:
100000 3394 8049 2480 2385 15911 7429 5602 15925 11546 6639 18560 19104 3693 17136 3528 14542 10668 8296 10166 365 9208 9397 18165 18824 17563 9187 9829 1600 13835 14607 14019 779 959 15795 9971 14175 16100 5613 15636 18410 18389 2719 8930 13864 18762 10205 16788 6402 19733 8768 1357 19211 4819 2466...
output:
402761186 744645778 906789151 17991697 774211658 792980765 696950150 348776668 172807511 497106032 966978624 54606150 626280145 56848129 841561846 861237209 349356249 320420130 475769907 515670862 202394241 992165822 730042803 54547059 810764077 643408786 645061981 149571157 714210069 785907778 4008...
result:
ok 100000 lines
Test #40:
score: 0
Accepted
time: 266ms
memory: 20424kb
input:
100000 14699 18279 6127 11662 2716 10526 17277 7876 1229 9997 18176 1922 18450 15765 19957 8261 12551 2552 8732 18341 12327 17365 19751 6262 14473 7185 7128 4518 2038 12513 3401 19331 11907 9386 10969 10790 3426 19180 4061 4028 1728 4128 6491 8938 796 4683 18174 12945 4255 12668 6110 19058 17352 696...
output:
482725228 593820109 693214110 925213055 45028810 380872656 110611798 16707825 235766194 527481452 480583151 656981174 624224505 156122646 305681012 294323014 407165495 260637125 330065004 944592977 760997301 27045450 626477413 234298445 748275601 893269818 689766054 898690240 961018886 802120794 764...
result:
ok 100000 lines
Test #41:
score: 0
Accepted
time: 281ms
memory: 21140kb
input:
100000 1343 5344 13446 18071 4477 1442 18239 12088 9867 4203 12294 10456 1657 8330 2473 14736 13338 14800 13371 10050 17580 12846 12916 4243 13504 17424 12011 1993 6014 7665 14788 17814 7953 12814 6925 16017 2529 15755 16599 11759 19669 13498 1948 12973 9350 155 11998 6253 317 11323 17201 8293 7371 ...
output:
939614124 126051169 551648864 200581427 628165391 905518050 612202254 341079695 711178715 559672624 655708868 102121912 631438927 847045186 963218305 180200507 842241961 469402922 2188373 434289161 961311360 502652503 241684447 910904204 735688450 615064582 479533657 785104364 398254971 63927996 542...
result:
ok 100000 lines
Test #42:
score: 0
Accepted
time: 289ms
memory: 21708kb
input:
100000 10963 3180 9155 7804 18337 2438 8153 11918 1024 1406 1065 7899 8443 12171 11556 7891 13116 1633 6772 19407 17630 184 9647 7530 16738 10661 17164 17837 2199 14686 14168 4289 11723 9601 11230 7950 3759 18380 8530 6999 11907 3010 14497 9641 10913 9394 1142 10055 19762 2158 14592 18385 970 2842 8...
output:
879395485 939922115 578868447 175035800 22597204 696705379 476380523 79448851 254219364 804082919 524323153 252152345 852515908 751772944 479701650 545672489 788131375 544805574 467694083 721958081 269698834 651670818 779193452 803915458 731557234 966203455 363296972 629014727 608326138 762858159 83...
result:
ok 100000 lines
Test #43:
score: 0
Accepted
time: 286ms
memory: 22380kb
input:
100000 7815 6488 12766 763 730 18858 15257 1796 18613 5154 188 14952 13227 14568 13328 9262 8641 5641 10145 15027 18222 8447 6729 19554 246 4233 15189 8492 11891 16855 4861 9731 19780 8323 17247 6421 6991 11233 8739 3746 14014 5791 2257 2691 9942 8216 16376 18278 11162 1720 8596 18878 5263 14849 116...
output:
835838773 154579792 723439291 605490362 807167004 326413907 188156192 988660340 256573542 901740059 770718652 816204226 637247082 770739890 665759674 818898291 808892261 674188745 489465750 818230404 231677935 580202792 461695100 262596110 560553435 558551542 706459720 715322665 318089895 399171650 ...
result:
ok 100000 lines
Test #44:
score: 0
Accepted
time: 300ms
memory: 23032kb
input:
100000 2300 17506 7790 15991 16179 19427 9293 11363 18382 15086 8716 16312 11237 5520 9127 7012 12227 11413 18702 3526 18650 9046 2937 6683 15897 4438 7299 1677 1575 258 4584 15858 4529 5141 7802 19522 5382 17477 5642 8558 14265 12788 9087 6172 6683 13932 4474 12912 11412 2802 8905 2872 11347 534 13...
output:
490191997 494949213 833936995 74692916 786214312 536868249 496494153 410471823 131282162 810388506 344893449 228597933 274181521 138615262 113181101 932450752 47199556 659650768 665259728 953022711 881408606 849503621 974800206 613761270 640692776 130734848 172853182 853301813 736950007 502539670 64...
result:
ok 100000 lines
Subtask #6:
score: 30
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Dependency #5:
100%
Accepted
Test #45:
score: 30
Accepted
time: 270ms
memory: 17932kb
input:
100000 14874 9745 15576 5667 15367 19726 17023 7247 19645 6093 4247 2414 6081 2883 15499 19924 13304 3042 19494 10806 1852 11015 18113 17260 1347 9940 15506 12240 4124 10051 10695 16303 11497 9391 18649 3331 6931 11987 13319 9887 5071 2346 3703 14520 19089 7957 17102 18804 197 13536 12240 12342 9478...
output:
640681511 903486727 496600600 874222455 633953780 770621896 671445287 529850353 471686990 260013146 757679541 154035467 488564448 33333313 744055768 436953930 358618653 130322264 454489853 745738790 156965269 472943924 435758830 893307594 395531745 189343204 671969380 198905218 264975839 460794303 3...
result:
ok 100000 lines
Test #46:
score: 0
Accepted
time: 274ms
memory: 18604kb
input:
100000 14505 17400 11510 10401 19273 15628 12668 16471 3689 998 10591 18108 6595 4360 8577 10428 12565 4721 439 7196 3718 12858 15956 10236 14630 5638 10626 10154 15037 10803 12264 12369 14321 10994 6380 19902 13614 4768 17390 5917 3189 16298 13359 7880 7349 14885 19147 8669 12405 18645 13314 2444 7...
output:
660479013 312577446 16795457 927153631 965129284 575317977 257997573 642936813 970599872 348672507 562667136 463021157 906085267 343297982 12179015 539951939 868064416 801295493 282030196 668402761 330923411 381937833 691331572 663363145 449168021 422659678 796118194 495284796 733118457 148751677 10...
result:
ok 100000 lines
Test #47:
score: 0
Accepted
time: 282ms
memory: 19512kb
input:
100000 18851 9354 6917 6466 18579 6574 2837 15862 16282 391 15213 17640 3726 19736 11467 5971 1963 7918 4972 15670 13614 2848 11102 6972 10054 846 13895 1290 8629 4781 19086 16827 9371 15215 3692 10131 5827 15427 6035 2623 18187 7900 9122 2908 15268 4139 1637 15141 3159 1074 17226 1271 6957 17979 70...
output:
137163734 954213047 473193230 527734958 934126924 683784314 563537801 254881331 115772927 937111255 742465762 502563699 542228119 317474339 709293921 810123162 269791643 854855789 444345585 42668520 789137257 130763828 877571276 500199866 689326579 949674294 55018412 867462590 288619865 808658431 75...
result:
ok 100000 lines
Test #48:
score: 0
Accepted
time: 297ms
memory: 20288kb
input:
100000 11291 17019 12000 6313 15183 7609 14663 6048 5164 5443 3159 10467 610 15460 19401 13288 16457 12801 10364 2555 5139 449 12660 11591 13726 13117 4206 18693 17060 1369 16276 13110 1636 629 766 13549 16985 15505 15795 10068 18034 1206 7401 12574 17664 14460 3259 18820 6310 18203 5641 2422 11920 ...
output:
702158338 112046096 987311637 686735002 653875049 494742619 583271838 996203276 991341095 691320080 624451739 739524593 299545653 1274690 758287704 961387470 557774100 482253278 191571291 445689046 887579872 285671487 910721909 941511457 592487451 675218616 640317690 809683141 836232651 532472126 51...
result:
ok 100000 lines
Test #49:
score: 0
Accepted
time: 305ms
memory: 21072kb
input:
100000 12091 4713 5901 19383 19586 3981 16325 625 5659 3705 11695 2414 676 18074 15045 19772 17966 6506 8936 6749 18739 18437 5799 13864 16302 243 1760 7392 5528 922 1157 4523 12934 12631 8220 5210 11746 2536 15494 1275 19420 1647 14848 14269 2188 3014 18090 18223 5205 788 16469 17754 6 8791 10803 1...
output:
641950593 528612175 420849683 888624102 713016942 736512413 534976538 906602055 337640938 170475135 481648210 529809518 12526637 481918068 517141052 6609273 920919623 870152129 157015053 324402319 232001584 942119385 601591456 78204600 574371073 176300408 533194290 197123379 229428082 777466269 1001...
result:
ok 100000 lines
Test #50:
score: 0
Accepted
time: 328ms
memory: 21748kb
input:
100000 15274 19792 12125 18442 580 12001 5602 6523 10729 11031 3966 6964 8984 5 15396 368 4770 18149 14132 18013 4087 13116 11380 4391 18896 12167 18265 3395 4014 16656 16050 1835 9116 4456 3936 1214 8108 10979 2811 11752 375 19297 6808 2745 7313 2322 13662 9902 13353 4714 4702 10840 3620 6147 4445 ...
output:
130086680 167157438 24744530 399057103 512746095 268605580 408156765 983275571 720719391 957664978 125357399 536149355 294633002 212817780 25089374 903267487 27278455 609688569 448706462 264818028 139560208 82259553 562394273 329983160 48637672 799860316 117827809 464473726 962947299 637272422 61076...
result:
ok 100000 lines
Test #51:
score: 0
Accepted
time: 326ms
memory: 22704kb
input:
100000 19146 17186 3518 19438 14943 13689 8203 14065 3943 18560 9193 7612 14119 10895 17866 18353 5956 10155 14329 18943 4561 3871 19678 11255 11705 2907 11376 11986 18253 10604 8971 7794 17935 13292 10011 2230 7608 2572 10876 4392 6829 10797 12740 5998 759 7801 10131 17035 8150 7327 9458 4982 9940 ...
output:
612904942 722282243 717726747 637619297 492358755 434278742 228364771 754524184 796939801 609081674 244643311 403383912 906368667 841542503 874340169 30477032 923939528 362940473 19653736 269906119 454441619 711796567 690519929 549808642 732679823 281494181 838882033 71833807 247742051 238051613 765...
result:
ok 100000 lines
Test #52:
score: 0
Accepted
time: 340ms
memory: 23484kb
input:
100000 10066 6264 15801 1403 163 16073 2834 9501 11876 18840 5750 19306 12711 9861 18661 8603 5620 1286 7942 10511 19118 10496 13111 1442 10989 4102 2935 11948 13733 6303 2768 16940 2980 9519 7494 15205 5922 3485 9865 13601 19208 6687 9143 17985 2724 16856 6494 17507 12790 17597 3826 8940 11916 1232...
output:
142394668 709638743 83326431 13545744 192327814 923541733 247661424 474656431 871310257 778938692 125162712 72037226 480892115 709457912 997858671 633056016 310524672 245075813 573271171 27826583 80737446 285061156 114578686 655222828 513728090 792570831 710229981 20531189 870845357 297825484 410305...
result:
ok 100000 lines
Test #53:
score: 0
Accepted
time: 368ms
memory: 24164kb
input:
100000 14632 7832 3132 784 1427 8593 13462 9275 8520 1604 2552 19506 17782 17537 16418 12225 8982 7888 2228 4534 14098 10589 7555 9025 17097 18528 7397 16909 7898 9196 11122 9214 16570 12646 18213 11368 18686 1113 854 15213 4220 5010 14318 11143 12921 14109 15979 14034 19897 17108 14720 17566 10410 ...
output:
858252942 303699608 224035512 884924303 554386423 232110474 558456014 51095327 979607100 452948735 552544146 435798967 886502003 151435770 950114399 820981016 366152337 890415849 798251380 873275888 153511409 134424711 29247165 187194469 772045462 888512414 668056537 426749014 339899115 765272222 80...
result:
ok 100000 lines