QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313444 | #8127. Slučajna Cesta | Crysfly | 40 | 156ms | 38768kb | C++17 | 2.5kb | 2024-01-24 19:20:05 | 2024-01-24 19:20:05 |
Judging History
answer
// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define mod 1000000007
struct modint{
int x;
modint(int o=0){x=o;}
modint &operator = (int o){return x=o,*this;}
modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
modint &operator ^=(int b){
modint a=*this,c=1;
for(;b;b>>=1,a*=a)if(b&1)c*=a;
return x=c.x,*this;
}
modint &operator /=(modint o){return *this *=o^=mod-2;}
friend modint operator +(modint a,modint b){return a+=b;}
friend modint operator -(modint a,modint b){return a-=b;}
friend modint operator *(modint a,modint b){return a*=b;}
friend modint operator /(modint a,modint b){return a/=b;}
friend modint operator ^(modint a,int b){return a^=b;}
friend bool operator ==(modint a,modint b){return a.x==b.x;}
friend bool operator !=(modint a,modint b){return a.x!=b.x;}
bool operator ! () {return !x;}
modint operator - () {return x?mod-x:0;}
bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}
vector<modint> fac,ifac,iv;
inline void initC(int n)
{
if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
int m=iv.size(); ++n;
if(m>=n)return;
iv.resize(n),fac.resize(n),ifac.resize(n);
For(i,m,n-1){
iv[i]=iv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
}
}
inline modint C(int n,int m){
if(m<0||n<m)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f
int n,fa[maxn];
modint a[maxn],f[maxn];
vi e[maxn];
modint dfs(int u,int pa)
{
int cnt=0;
modint sum=0;
for(int v:e[u]){
if(v==pa)continue;
modint w=dfs(v,u);
cnt+=1;
sum+=w;
}
modint res=(1-qpow((mod+1)/2,cnt));
res*=sum/cnt;
// cout<<"res "<<res.x<<"\n";
res+=a[u];
return res;
}
signed main()
{
n=read();
For(i,2,n)fa[i]=read(),e[fa[i]].pb(i),e[i].pb(fa[i]);
For(i,1,n)a[i]=read();
For(i,1,n)cout<<dfs(i,0).x<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 34956kb
input:
2 1 307903 536004
output:
575905 500689959
result:
ok all correct
Test #2:
score: 10
Accepted
time: 0ms
memory: 35104kb
input:
3 1 2 992649 690492 637324
output:
1497226 876301738 251230734
result:
ok all correct
Test #3:
score: 10
Accepted
time: 4ms
memory: 35780kb
input:
4 1 2 3 826918 524416 30987 233038
output:
501126006 889825 375470082 250483002
result:
ok all correct
Test #4:
score: 10
Accepted
time: 4ms
memory: 36580kb
input:
5 1 2 3 4 859332 957641 552087 294350 114098
output:
126520100 939052817 751204107 938304296 125572709
result:
ok all correct
Test #5:
score: 10
Accepted
time: 5ms
memory: 36276kb
input:
6 1 2 2 4 5 91742 92552 191745 529457 181043 884683
output:
47206686 156670572 984787945 922712805 617936136 829257432
result:
ok all correct
Test #6:
score: 10
Accepted
time: 0ms
memory: 34916kb
input:
7 1 1 3 4 4 6 69032 207537 280790 889967 218886 618588 754535
output:
293473187 945792944 24287651 511768034 204044442 255223945 87278766
result:
ok all correct
Test #7:
score: 10
Accepted
time: 6ms
memory: 38768kb
input:
8 1 2 2 4 2 6 7 546075 347525 670520 983062 581593 336046 97830 706738
output:
334418635 329187863 605358267 243713478 246081337 164970462 770221487 347328072
result:
ok all correct
Test #8:
score: 10
Accepted
time: 0ms
memory: 36172kb
input:
9 1 2 3 3 5 1 7 8 817515 848951 198209 119142 819728 367379 501231 458709 804045
output:
778945070 884374888 701481221 254592128 137000383 674805839 311894676 750233527 417348933
result:
ok all correct
Test #9:
score: 10
Accepted
time: 4ms
memory: 34908kb
input:
10 1 1 1 4 5 4 1 8 8 874755 324368 592836 600006 266724 217696 423188 402322 557734 423393
output:
616715460 217237546 634133532 688080628 590912992 60727477 121167098 530612063 430789154 868180005
result:
ok all correct
Test #10:
score: 10
Accepted
time: 0ms
memory: 35764kb
input:
10 1 2 3 1 5 6 7 7 9 195744 206104 723327 114978 178292 190130 540646 250919 152931 940237
output:
158806482 79765837 290477198 526950480 317003915 633487763 313413032 531963588 860175194 157463149
result:
ok all correct
Test #11:
score: 10
Accepted
time: 4ms
memory: 36628kb
input:
10 1 2 2 4 5 4 7 1 9 160335 133086 186701 906673 561321 529327 813569 759454 327734 62760
output:
612909843 659626152 629535210 48467043 569673492 130085768 77772881 52282583 56718813 704471661
result:
ok all correct
Test #12:
score: 10
Accepted
time: 0ms
memory: 36876kb
input:
10 1 2 2 1 5 6 7 8 9 286342 884910 904819 108098 292165 78969 566381 587683 156711 111976
output:
821283130 567751781 374520609 61373271 149275061 51484565 229512794 771472918 448321820 132272409
result:
ok all correct
Test #13:
score: 10
Accepted
time: 9ms
memory: 35120kb
input:
10 1 1 3 3 5 6 6 6 9 820907 494966 187493 466984 150135 896410 388758 105418 191024 930665
output:
363066644 242278836 612403907 108326578 274335852 819650079 613004775 29429418 811535270 291689673
result:
ok all correct
Test #14:
score: 10
Accepted
time: 4ms
memory: 34924kb
input:
10 1 2 3 4 5 5 7 7 9 780617 360476 946142 170041 984436 863484 705401 759288 364152 323780
output:
792343871 562727727 562167115 91166936 840366602 290796618 770432943 924365902 661973330 774831032
result:
ok all correct
Test #15:
score: 10
Accepted
time: 9ms
memory: 35644kb
input:
10 1 2 2 1 5 5 1 1 9 996177 507917 928080 610241 428655 745973 313129 879790 3630 222636
output:
585661496 324752716 780879684 93121435 366439393 584327336 833975652 801152444 944125266 629583216
result:
ok all correct
Test #16:
score: 10
Accepted
time: 0ms
memory: 35780kb
input:
10 1 2 3 4 5 6 7 8 9 485357 872875 543104 252486 738854 873509 801028 59862 417026 867486
output:
739460169 733862443 778669222 462141515 876563208 978255004 317930623 65403099 345776883 397765700
result:
ok all correct
Test #17:
score: 10
Accepted
time: 0ms
memory: 34868kb
input:
10 1 1 3 1 5 6 6 8 5 405829 249733 974377 17147 381677 349987 698528 659718 383030 547497
output:
828512375 738117175 280840778 603744319 264086975 110768674 214583133 895570339 763890880 911231948
result:
ok all correct
Test #18:
score: 10
Accepted
time: 9ms
memory: 35412kb
input:
10 1 2 3 1 5 6 7 8 7 114148 888405 653482 324506 212949 908169 155568 180096 181076 166389
output:
809474092 686924034 656473190 604449927 836836772 782500753 768863726 321788284 881297985 199739646
result:
ok all correct
Test #19:
score: 10
Accepted
time: 0ms
memory: 34900kb
input:
10 1 1 3 4 5 6 7 6 9 878639 541255 25599 274902 119473 639010 97108 753448 96106 773930
output:
983622610 739341242 903019368 274169390 281959300 123432644 720471011 147529573 361101388 741298692
result:
ok all correct
Test #20:
score: 10
Accepted
time: 9ms
memory: 36052kb
input:
10 1 2 2 2 2 2 2 2 2 766887 885978 73938 216251 903006 615990 205756 890530 603065 506057
output:
671137547 284402329 811845161 839566505 932739803 157080025 982378930 332142162 366784703 464349985
result:
ok all correct
Test #21:
score: 10
Accepted
time: 0ms
memory: 36716kb
input:
10 1 2 3 4 5 6 7 8 9 733342 202778 673543 829195 415681 35504 602267 386331 559518 466392
output:
735524386 852512262 329450881 470194237 94855921 266434302 571422189 161172655 331123819 887672425
result:
ok all correct
Test #22:
score: 10
Accepted
time: 0ms
memory: 36684kb
input:
10 1 2 2 1 4 4 6 3 8 904213 323773 607336 184293 233574 392314 370246 454542 257726 448337
output:
590656244 75229314 856033476 756000651 60461972 354421829 289846343 833907290 404114388 639532023
result:
ok all correct
Subtask #2:
score: 30
Accepted
Test #23:
score: 30
Accepted
time: 10ms
memory: 35436kb
input:
100 1 2 1 4 5 6 7 7 9 9 5 12 5 4 1 16 17 18 18 20 20 22 23 24 25 23 27 28 27 30 31 32 27 34 35 36 37 38 39 39 41 38 43 43 45 46 43 48 49 49 49 48 48 54 55 56 57 57 55 60 60 62 55 64 65 64 67 67 69 69 69 72 37 74 75 76 76 78 76 80 81 82 80 84 85 74 87 87 89 89 91 89 87 94 94 96 97 98 98 754341 720186...
output:
744419112 868534785 579276734 966426530 89470157 365627670 936462279 93017671 603359319 522390035 22343082 205462129 636979071 211558039 86006737 525095665 167727115 994038924 460586504 309146514 877389799 199845255 163729135 868507823 372639715 82379059 856574083 348017654 982070262 781505719 17297...
result:
ok all correct
Test #24:
score: 30
Accepted
time: 11ms
memory: 35292kb
input:
200 1 1 3 4 5 6 7 8 8 5 11 12 13 13 15 16 16 18 19 20 21 22 23 16 25 25 27 28 29 30 31 28 33 28 35 35 37 35 13 40 41 42 40 44 45 46 47 45 49 50 50 52 53 52 52 56 56 58 58 60 56 62 62 62 65 65 67 68 65 70 71 65 73 73 75 75 77 77 79 80 79 82 83 84 83 86 87 87 89 90 91 92 92 94 92 96 97 98 96 92 101 10...
output:
725084368 983709498 824961909 336358280 709426657 297523596 426557566 767786580 119003107 931503705 534694332 425258617 150579774 654744506 642042232 884679319 138214497 181144455 893410053 52582794 987525977 416233639 552678811 618456103 941998026 784721349 218719610 952238453 248625961 515894278 7...
result:
ok all correct
Test #25:
score: 30
Accepted
time: 19ms
memory: 35424kb
input:
300 1 1 3 3 5 6 7 8 9 10 10 12 13 13 15 15 15 18 19 18 21 22 23 24 25 26 26 28 29 29 31 32 33 34 31 36 36 36 39 24 41 42 41 44 44 46 46 48 49 50 51 52 51 48 55 56 57 57 57 56 61 62 63 63 65 65 67 68 65 70 65 72 73 74 73 76 76 78 79 80 81 82 83 84 84 86 86 81 89 90 90 92 90 94 95 95 97 97 99 99 101 1...
output:
245228535 330574102 623747432 347404985 841330143 377311095 101979551 376122688 338441219 182393713 197828758 67681752 944133369 483788933 74252544 239292125 10620946 809868775 90567869 977253962 373790456 974815708 812859891 573734099 770042308 506972531 441953277 671648793 804831163 642858219 5873...
result:
ok all correct
Test #26:
score: 30
Accepted
time: 27ms
memory: 34956kb
input:
400 1 2 2 4 4 6 7 7 9 9 11 12 12 14 15 16 17 18 19 20 17 22 22 24 6 26 27 27 29 30 31 32 31 34 35 31 27 38 38 40 41 42 43 44 43 46 47 48 49 50 51 51 50 54 54 56 57 56 59 60 60 62 60 64 65 64 64 49 69 70 70 72 73 74 70 69 77 78 79 80 43 82 82 84 82 86 87 86 89 82 91 92 93 94 94 96 97 96 99 100 94 102...
output:
754332851 602516582 858960349 394861150 370101800 818086925 381161276 772456843 533357677 923445686 533256367 446071355 358631457 792990398 767235134 374957506 563570675 39871177 770504510 886075159 591304517 272762925 568365410 973459255 815692541 497998120 151711203 35325302 537107679 467417192 52...
result:
ok all correct
Test #27:
score: 30
Accepted
time: 38ms
memory: 36120kb
input:
500 1 1 3 4 4 6 7 8 7 10 11 11 10 14 15 15 17 18 19 20 21 22 20 20 15 26 1 28 29 28 31 31 33 33 35 36 37 38 39 40 41 42 41 44 45 45 45 48 48 50 51 51 53 54 54 45 57 57 45 35 61 62 62 64 64 66 67 68 66 66 71 72 73 74 75 76 76 76 79 79 71 82 83 84 83 83 87 87 89 90 90 90 90 66 95 96 97 95 99 33 101 10...
output:
906511411 413531698 745505573 641643624 662863268 401252230 595706839 42431125 362173724 700649975 179990748 187809670 187389614 670195856 817888726 179822185 318036156 415931158 221538951 759090116 79610140 321151639 964539521 517058362 600541445 486856458 241771164 885795312 751536190 334841583 31...
result:
ok all correct
Test #28:
score: 30
Accepted
time: 53ms
memory: 36848kb
input:
600 1 1 3 3 5 6 7 8 9 10 9 12 13 14 15 14 17 18 17 20 13 22 22 24 24 22 27 22 29 29 31 32 33 34 33 36 37 32 39 40 39 42 42 44 45 46 47 48 13 50 51 1 53 54 55 56 56 55 59 60 61 55 63 64 64 66 63 68 69 55 71 72 73 74 74 72 77 77 79 80 81 81 83 84 81 86 87 88 89 55 91 91 93 93 93 96 97 98 98 91 101 102...
output:
663139314 649624699 751037743 473869401 196678294 968269744 472882712 213799472 421260937 641073389 760627003 257912082 616548809 662549687 547402110 364876691 229947924 20337318 847324789 512030620 925329816 600788387 714887131 727246386 691159491 441218441 90415548 477248289 423098965 201224028 60...
result:
ok all correct
Test #29:
score: 30
Accepted
time: 71ms
memory: 36340kb
input:
700 1 2 2 4 1 6 6 8 8 6 11 12 13 12 11 16 17 17 19 20 21 22 21 24 25 25 27 28 29 30 30 30 25 34 35 34 37 38 17 17 41 41 43 44 43 46 47 48 49 50 47 52 41 41 55 56 57 58 59 60 57 62 63 64 64 66 66 68 62 70 70 72 55 74 75 76 76 78 79 80 78 82 83 84 83 86 87 88 88 90 91 90 93 90 78 96 97 98 97 100 101 1...
output:
570872379 237182013 688066 86834668 641516489 591491574 3158251 59233535 333219945 270152432 668422598 235996748 622223543 998639327 714391301 493516651 985359148 628204166 746819282 529690805 34279739 680252229 953391073 928607169 631197490 144333434 682858220 457488682 210043864 662617590 75057910...
result:
ok all correct
Test #30:
score: 30
Accepted
time: 98ms
memory: 35560kb
input:
800 1 2 3 4 4 6 7 4 9 10 11 11 11 2 15 16 16 18 19 19 19 19 23 23 25 23 27 28 29 30 31 32 30 34 35 34 34 34 39 19 41 41 43 41 45 41 47 48 49 48 48 52 47 54 16 56 56 58 59 59 61 61 63 64 65 63 67 68 69 68 67 72 73 61 75 76 77 77 76 80 81 82 83 84 85 86 84 88 88 90 83 92 81 94 95 96 97 81 99 100 101 9...
output:
233496187 599291184 479012731 855127161 401991189 274677969 418543687 362349277 577701995 828969207 816848399 495058149 328423591 78078113 161123890 815238539 473019428 878535442 18674067 835577888 463623498 897658423 213366930 848188502 542963887 862188865 584746388 174480342 100279923 173069394 96...
result:
ok all correct
Test #31:
score: 30
Accepted
time: 119ms
memory: 35688kb
input:
900 1 2 3 4 5 5 7 8 4 10 11 11 13 14 15 16 3 18 19 19 19 19 23 23 23 26 27 28 29 30 31 32 33 34 35 36 34 38 39 40 33 42 43 43 45 45 47 48 48 45 51 52 53 52 51 56 57 57 57 31 61 61 63 61 65 19 67 68 69 69 71 72 73 71 75 76 77 78 79 79 81 82 78 84 84 76 87 88 88 90 91 92 92 94 94 96 91 98 98 100 101 1...
output:
481422270 722211524 968944619 873430456 569340426 696897242 960672903 855860632 237528392 803883698 282053334 922373608 482232420 171159441 945594423 192483984 712235134 176120775 245350023 332340008 460005442 166307245 144798528 279179169 591618709 652685782 617304045 890361202 107606344 627358135 ...
result:
ok all correct
Test #32:
score: 30
Accepted
time: 145ms
memory: 36332kb
input:
1000 1 2 2 4 1 6 7 8 6 1 11 11 13 14 15 16 15 11 19 1 21 22 23 24 24 26 27 28 28 1 31 32 33 32 32 36 32 31 39 1 41 42 43 43 45 42 41 48 49 1 51 52 52 51 55 51 57 58 59 1 61 62 62 64 62 66 67 66 69 1 71 71 73 74 75 76 77 78 79 1 81 82 82 84 82 86 87 87 89 1 91 91 93 94 95 95 97 98 97 1 101 102 103 10...
output:
860962935 342129626 68822226 457947417 472192430 663590072 528597324 421355230 30806031 980716344 775140697 855909014 685267513 433181261 645721034 637713641 91714280 996133261 790463317 277249991 361750689 880420626 88321325 560640892 48310409 106320979 749041052 477559724 289354988 414711535 70323...
result:
ok all correct
Test #33:
score: 30
Accepted
time: 145ms
memory: 36000kb
input:
990 1 1 1 1 5 6 7 6 9 9 1 12 12 14 12 16 17 18 19 18 21 1 23 23 25 25 27 28 28 30 31 31 1 34 34 36 36 38 39 40 41 34 43 1 45 46 47 48 49 50 50 48 53 53 1 56 56 58 58 60 61 62 63 63 62 1 67 68 68 68 71 71 73 74 75 73 1 78 78 80 80 80 83 80 85 85 87 1 89 90 89 89 93 94 93 96 96 96 1 100 101 101 103 10...
output:
566521970 19653884 957347745 785407324 95586701 595663598 610224234 823813619 540500089 776787780 651399838 54001866 445110629 76766067 968249950 791568580 802774970 111247619 471825425 147997418 565116118 210072282 451700816 317545773 814453618 488318872 555385352 116808350 807663467 714985382 4313...
result:
ok all correct
Test #34:
score: 30
Accepted
time: 147ms
memory: 35028kb
input:
996 1 2 3 4 5 6 5 3 9 9 9 1 13 14 15 13 17 18 13 20 21 20 23 1 25 25 27 28 29 30 31 31 33 33 25 1 37 37 39 40 40 42 42 42 45 46 45 1 49 50 51 50 53 54 55 56 54 58 53 1 61 61 63 61 65 66 66 68 61 70 71 1 73 74 73 76 76 78 79 78 81 82 82 1 85 86 87 87 89 90 90 90 89 94 95 1 97 98 99 99 98 98 103 104 1...
output:
748874153 262146514 794139762 417820957 298970407 382358247 5414946 103359054 855914104 123309747 81482823 101977388 92589265 523995204 605707038 320493045 125905537 969755207 63784176 441155209 154337970 20171151 114797496 410322060 50350007 762147631 420862102 377956803 22797731 429289375 49433594...
result:
ok all correct
Test #35:
score: 30
Accepted
time: 141ms
memory: 36268kb
input:
988 1 2 1 4 5 5 7 8 9 10 7 12 1 14 14 16 17 18 18 20 20 22 23 20 25 1 27 28 28 30 31 30 33 33 35 35 33 38 1 40 41 42 43 44 45 46 47 48 48 46 51 1 53 54 55 56 56 56 55 60 61 61 55 64 1 66 67 68 69 69 69 72 68 74 75 76 76 1 79 79 81 82 83 82 85 86 87 87 87 81 1 92 93 94 93 96 96 98 99 99 101 98 103 1 ...
output:
622685004 586644318 974784715 688575722 724649130 930489320 286767417 349766241 97171025 892488388 845049214 97843912 648810060 680152501 830749961 384209943 442923008 438908715 77100762 156169586 199275646 340907539 327084666 635293813 94536865 980218063 136570259 412676747 59973487 504052430 89769...
result:
ok all correct
Test #36:
score: 30
Accepted
time: 147ms
memory: 36700kb
input:
994 1 1 1 4 1 6 7 1 9 9 11 9 13 1 15 15 15 18 19 20 21 22 23 23 25 26 23 1 29 30 31 31 30 34 35 35 37 38 37 40 40 1 43 44 45 46 45 48 49 50 48 44 53 53 55 1 57 58 59 59 61 62 62 64 64 64 67 68 68 1 71 71 73 74 75 74 71 78 79 79 79 82 71 1 85 86 87 88 89 89 91 87 93 94 93 96 93 1 99 100 100 99 103 99...
output:
351906097 418196456 800116970 230924268 487732224 705400952 727810098 485486331 666494686 397372093 305762969 787863087 688737733 792978069 238014934 225927280 601615032 113511344 195873644 875314471 991863898 854453158 970927848 217035938 171182939 23494103 849454215 967280867 580937409 725333795 5...
result:
ok all correct
Test #37:
score: 30
Accepted
time: 141ms
memory: 36592kb
input:
990 1 1 3 3 5 6 7 8 9 6 11 12 13 12 1 16 17 18 18 20 20 22 23 22 25 25 25 28 29 1 31 32 32 32 35 36 35 38 35 40 41 42 41 44 1 46 46 48 49 50 51 52 48 54 55 55 57 57 48 1 61 61 63 64 65 66 67 66 69 70 65 72 73 72 1 76 76 78 79 80 81 82 78 84 85 78 87 87 89 1 91 92 91 94 95 95 97 98 95 100 100 102 103...
output:
171716349 826522197 827435960 246212111 496792282 831079660 507730844 942351412 846775580 231804575 612122929 222863497 705101267 386790628 553867612 357863959 754836419 28499939 464916813 916106291 187482558 949079915 316083445 294612216 836187764 655471514 842762710 355196854 709326425 222955504 8...
result:
ok all correct
Test #38:
score: 30
Accepted
time: 146ms
memory: 36476kb
input:
992 1 2 3 2 5 6 7 7 9 10 11 6 6 14 15 1 17 18 17 20 21 22 22 24 25 25 27 28 28 30 31 1 33 34 35 35 35 38 34 40 41 42 43 44 44 41 47 1 49 50 51 52 51 54 55 55 57 58 50 60 60 62 60 1 65 65 67 68 68 68 67 72 73 74 74 72 77 78 79 1 81 81 83 83 85 85 83 88 88 90 91 91 93 94 94 1 97 98 99 98 101 98 103 10...
output:
505943433 85278950 560248446 123470514 437750030 15710952 374500091 134365778 798108989 71698259 630177235 336715186 859789293 844790277 766492557 760998581 579309950 938348690 459037263 595363866 886814495 877183620 662048691 413415159 491837538 13315517 332259090 816351110 721503013 654603103 6712...
result:
ok all correct
Test #39:
score: 30
Accepted
time: 141ms
memory: 35264kb
input:
986 1 2 3 3 3 6 7 7 9 10 11 12 13 14 15 15 1 18 19 20 21 21 23 24 23 26 27 28 29 30 29 29 33 1 35 36 37 38 39 39 41 42 43 44 45 43 41 48 49 38 1 52 53 54 55 55 57 58 54 60 53 62 63 63 65 66 67 1 69 70 70 72 73 74 69 76 77 78 78 77 81 81 83 84 1 86 87 86 89 89 91 91 93 89 95 96 97 98 99 100 99 1 103 ...
output:
789218245 501848982 616046947 7000199 111177722 792623975 99891325 501768858 58464812 125064003 753684990 9085891 518545750 537283672 172606342 397255357 959173940 521699802 734185616 63210187 673894123 826131873 97288984 950373989 717039561 852849498 943754388 255730130 288272653 452945492 13579873...
result:
ok all correct
Test #40:
score: 30
Accepted
time: 150ms
memory: 36896kb
input:
990 1 2 3 3 1 6 7 7 7 10 11 12 12 14 7 16 16 1 19 19 19 22 23 23 25 23 27 28 28 27 31 32 32 32 35 1 37 38 38 40 41 37 43 44 45 46 47 46 46 50 51 51 53 1 55 56 56 56 59 60 59 56 63 64 65 66 67 68 69 68 71 1 73 73 75 76 77 77 73 80 80 80 80 84 84 86 86 86 86 1 91 92 93 94 95 94 97 94 99 100 100 102 10...
output:
347724386 434953828 278379318 277331845 214728081 610771529 6158178 838493203 752649405 625546702 705897575 258707468 952282066 940915211 211291782 175806819 309481836 121859538 701774437 345330893 32778931 124956075 497611432 957345086 483506862 155977179 86311048 54252523 446246284 8728605 5984218...
result:
ok all correct
Test #41:
score: 30
Accepted
time: 142ms
memory: 36272kb
input:
988 1 1 1 4 5 6 5 8 9 9 11 12 12 14 11 16 16 18 1 20 21 22 20 24 24 26 27 28 29 30 31 28 33 34 35 33 37 1 39 39 41 39 43 44 45 46 47 48 49 48 51 52 53 53 55 53 1 58 59 60 61 62 63 64 65 63 67 67 69 60 71 71 58 74 75 1 77 78 79 80 81 81 83 78 85 86 86 85 89 89 91 89 93 78 1 96 96 96 99 100 99 102 102...
output:
295346165 798770696 510413103 82785149 669919735 422081782 948196683 916989932 985940742 661260859 833440490 649736170 623252181 421209122 281291550 934402632 181083043 878638266 169498577 514714462 123035459 780926980 104155817 260206869 15540268 641771435 877529821 888185756 834604198 886452595 13...
result:
ok all correct
Test #42:
score: 30
Accepted
time: 143ms
memory: 36400kb
input:
1000 1 2 3 2 5 5 7 1 6 4 11 3 9 4 7 13 14 17 18 15 18 8 6 10 17 22 10 19 11 25 29 27 30 24 21 24 23 13 16 9 14 12 35 38 8 32 40 33 12 35 41 36 33 22 29 43 42 19 37 56 61 21 27 62 32 62 48 37 57 54 36 56 52 60 52 71 42 44 75 66 51 82 45 65 44 48 87 55 51 78 23 30 68 58 78 89 96 43 86 97 34 49 83 25 8...
output:
687945387 546383013 463784605 247575625 486788744 62343156 665815813 67847197 55185459 824173197 162695259 242054167 663563775 763117213 593920999 79360217 317731608 531031619 40724107 725867357 226274624 810222907 44373511 39379307 572995347 713209541 930765550 234054701 878624249 496121150 4119486...
result:
ok all correct
Test #43:
score: 30
Accepted
time: 148ms
memory: 36544kb
input:
1000 1 1 3 3 2 6 2 6 9 4 8 5 9 7 8 16 14 13 4 19 21 14 17 11 19 18 16 24 24 7 13 15 12 29 28 12 35 22 27 33 22 21 43 26 43 26 47 10 45 10 39 42 34 49 47 49 41 42 25 20 23 53 39 41 30 40 33 38 27 48 30 56 18 44 69 68 75 48 51 73 59 37 40 78 37 69 70 82 85 31 36 52 77 89 34 94 94 57 85 63 20 101 63 58...
output:
509639546 447230120 270271799 999513991 211596126 429563279 957584143 568844413 868522798 534386729 473218386 660177319 649956576 1526408 703544068 195817016 207805950 617740539 647080663 491157853 830085182 701022021 879195878 900000706 864193753 383201443 258728349 836786103 371782725 173986990 76...
result:
ok all correct
Test #44:
score: 30
Accepted
time: 156ms
memory: 35724kb
input:
1000 1 1 2 3 2 4 7 7 8 4 3 6 13 11 10 10 14 5 19 14 13 19 6 5 16 21 12 16 21 29 29 11 33 24 34 35 17 8 18 22 30 22 31 44 28 37 35 32 47 15 51 28 12 31 25 38 37 32 58 57 49 52 61 47 18 34 26 27 43 36 44 71 54 42 49 24 30 39 71 40 55 73 77 79 45 80 20 74 25 66 20 9 15 65 72 83 68 50 68 77 62 102 55 62...
output:
580578034 924246152 913399538 703655322 984158 301660688 697315862 993744950 156424374 485299106 809681185 678482784 538154743 869312897 121977664 940019480 570631749 662384090 975333965 477959769 892825183 597127681 867493058 331326215 974820246 714441040 243600775 465464397 109308308 270486564 480...
result:
ok all correct
Test #45:
score: 30
Accepted
time: 150ms
memory: 36276kb
input:
1000 1 1 3 4 2 6 7 8 3 8 9 12 11 12 4 7 14 14 13 5 2 11 13 5 25 22 16 21 22 21 10 10 26 28 25 36 18 33 27 30 24 20 26 41 27 36 31 39 46 30 39 38 29 31 42 37 33 17 29 38 6 54 54 44 20 40 47 35 56 34 57 43 9 51 67 44 64 34 55 23 58 58 15 17 82 80 73 85 47 68 80 42 81 86 75 92 87 82 83 49 68 52 23 53 8...
output:
125093706 704739815 102083849 279307769 271258078 819936910 620508746 524442890 554584666 782450571 434528173 70403377 827932445 964312269 816262054 884778219 414025116 785799824 324367831 124151976 275394760 34724066 550144093 522437131 300633676 423178949 330589144 838103761 434323011 69245398 998...
result:
ok all correct
Test #46:
score: 30
Accepted
time: 150ms
memory: 36668kb
input:
1000 1 1 2 4 5 3 7 4 8 3 5 8 10 13 14 7 12 17 19 14 15 20 23 2 9 10 26 21 21 12 23 13 25 15 25 31 17 27 24 31 6 18 32 37 40 26 29 37 39 27 29 16 20 24 32 56 36 22 19 40 47 58 45 58 35 63 38 44 65 33 34 51 69 47 74 62 48 64 72 30 70 70 61 34 52 84 50 60 62 35 85 51 65 38 64 72 52 6 73 16 49 43 94 41 ...
output:
423889453 363861048 59128790 972909604 755594617 397299818 49744452 864548563 216668395 433199925 542401571 362740165 484236228 28452270 283123170 578429970 716917589 261218228 693965878 453694984 667100806 203273997 829932215 657244822 196827637 599090703 559389359 741241575 249277413 612231321 194...
result:
ok all correct
Test #47:
score: 30
Accepted
time: 145ms
memory: 35136kb
input:
1000 1 1 3 3 5 5 7 8 8 10 10 12 8 8 15 16 17 18 18 20 21 17 23 24 24 26 7 28 29 28 31 32 32 34 35 36 36 36 39 39 41 42 43 44 45 46 43 48 49 49 49 52 53 49 55 56 57 57 59 57 61 62 62 64 65 66 67 68 67 70 71 72 73 74 74 64 77 49 79 80 81 82 82 84 82 86 87 88 86 90 91 92 93 93 95 96 97 97 99 100 99 102...
output:
588909236 809333062 274232845 649764930 862786045 331745643 19377577 149964644 632538200 798978725 567371111 527404637 268681708 663945980 75749893 422819549 565554395 116891266 468347509 898265341 324742101 883623856 412322600 365213634 637175795 954270110 53007126 376535767 78875956 303151737 7531...
result:
ok all correct
Test #48:
score: 30
Accepted
time: 149ms
memory: 34884kb
input:
1000 1 2 3 4 5 5 2 8 9 8 11 11 13 14 15 14 17 1 19 20 21 21 20 20 25 25 27 28 20 30 30 20 33 34 34 36 37 38 37 40 41 33 43 43 43 46 47 48 49 43 51 52 52 51 55 56 57 58 58 57 61 62 63 57 65 65 67 65 69 70 69 72 72 74 74 76 76 78 76 80 81 82 72 84 84 86 84 88 89 90 89 92 93 94 92 96 96 98 99 100 99 10...
output:
446128953 771846193 353581030 641992303 282359178 172760761 110824105 210873333 164551930 443644297 500282360 759533350 151181150 677005730 782470503 521521232 922591322 115341649 935429532 321221849 554037403 258492425 70923362 624831335 441181533 444773520 998121344 437321692 791730488 72633192 85...
result:
ok all correct
Test #49:
score: 30
Accepted
time: 147ms
memory: 36220kb
input:
1000 1 2 1 4 5 6 7 7 9 10 9 4 13 14 15 16 17 17 17 20 21 21 23 24 25 25 21 28 29 30 31 29 33 17 35 35 37 38 39 40 40 42 42 44 44 38 14 48 48 50 51 52 53 52 55 56 57 52 59 60 59 62 63 64 62 66 67 66 69 69 71 72 73 73 73 76 77 77 79 80 81 82 83 84 85 86 84 88 89 90 88 88 93 88 95 96 96 98 99 100 99 98...
output:
654471914 546615139 947922048 153503048 927630717 34223875 720388683 624306296 655456589 493083987 162073331 635838124 369929303 821333236 550440341 545680814 718752631 583115422 974066149 970294098 83094502 529671142 926147748 440592283 656733466 993666437 369100852 386989615 894289686 451198654 81...
result:
ok all correct
Test #50:
score: 30
Accepted
time: 145ms
memory: 36032kb
input:
1000 1 2 1 4 4 6 6 8 9 10 11 12 12 9 15 8 17 1 19 20 21 21 23 21 19 26 26 28 29 30 26 32 33 34 35 36 36 38 39 38 32 42 43 43 45 42 47 47 49 50 50 26 53 53 53 56 57 56 56 60 61 61 63 64 65 66 66 68 68 70 71 72 72 68 75 76 77 77 79 80 81 82 79 79 85 86 87 65 89 89 91 92 93 89 95 96 95 98 98 100 98 102...
output:
273532484 654900746 436901865 756951444 254519896 330002995 766044403 657460442 745446314 216201924 409558282 471338773 294275946 357142440 886431363 257567760 860256462 73649121 723536403 211807232 756732344 440886399 34106368 189767637 336626138 626005472 417874102 19728680 729174453 552154932 534...
result:
ok all correct
Test #51:
score: 30
Accepted
time: 146ms
memory: 36660kb
input:
1000 1 2 2 4 5 4 7 8 9 10 9 9 13 14 15 14 17 18 19 20 21 21 23 23 25 23 27 28 29 30 30 32 32 32 35 36 37 38 36 35 41 42 42 28 21 46 47 48 48 46 51 52 53 53 55 8 57 58 59 60 59 62 58 64 65 66 67 67 69 69 69 69 73 73 75 76 77 78 78 80 81 82 83 84 85 85 69 65 89 89 89 92 93 92 95 92 97 98 97 100 101 10...
output:
725195196 613825412 600466575 988748057 848020147 898988028 894024440 812375964 126387118 12947424 758813173 48614630 831378166 501730144 518516178 262917238 636605147 339884843 211964574 439677203 686412818 944085138 603580837 5265397 777691070 602160082 70957755 414236280 230808563 310343986 28932...
result:
ok all correct
Test #52:
score: 30
Accepted
time: 153ms
memory: 35252kb
input:
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...
output:
313566704 94576682 1320726 907941445 266980443 9723392 6237132 506086800 508113157 513847305 276737286 926631954 539407134 921768459 514471445 113377640 768934724 558859508 128223730 510892069 648378489 108521218 373281868 323396513 185226376 389161363 37575819 453296146 345134729 159169406 51433570...
result:
ok all correct
Test #53:
score: 30
Accepted
time: 145ms
memory: 35956kb
input:
1000 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2...
output:
908125419 945014005 688802237 69758801 690902928 728264629 497206206 758219731 743444429 834292230 94670858 192305546 567678971 33262989 936582856 84809030 931316352 956530676 703737368 950055104 464254266 694273301 874304574 11822831 683439534 180219586 868835018 32164593 42017275 855077189 5708268...
result:
ok all correct
Subtask #3:
score: 0
Time Limit Exceeded
Test #54:
score: 0
Time Limit Exceeded
input:
60000 1 2 2 1 3 4 5 6 9 6 11 11 13 8 4 10 7 10 3 16 12 9 19 15 24 24 27 25 8 16 13 7 20 15 22 28 33 31 20 27 41 17 25 35 39 5 22 34 19 14 49 34 51 31 39 56 55 48 48 14 47 50 58 12 61 41 66 21 62 64 57 32 54 30 30 50 45 40 56 38 38 43 76 44 84 49 59 84 66 45 57 60 47 42 33 54 74 37 59 26 18 101 80 67...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #79:
score: 0
Time Limit Exceeded
input:
100000 1 1 3 4 5 6 7 8 9 10 9 12 13 14 15 14 12 8 19 20 21 20 19 24 24 26 26 28 29 26 31 26 33 34 26 36 36 38 39 40 41 36 4 44 45 46 47 47 49 44 51 52 53 54 53 52 57 58 59 60 61 61 63 61 65 66 67 67 69 70 69 72 59 74 74 76 76 78 79 78 81 82 83 84 85 82 87 87 58 90 91 92 93 91 95 51 97 98 99 99 101 1...