QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#196176#5372. 杀蚂蚁简单版by_chance100 ✓450ms187172kbC++143.5kb2023-10-01 13:46:492023-10-01 13:46:49

Judging History

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

  • [2023-10-01 13:46:49]
  • 评测
  • 测评结果:100
  • 用时:450ms
  • 内存:187172kb
  • [2023-10-01 13:46:49]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
bool mem1;
typedef unsigned long long ull;
const int N=1e5+5,P=998244353;
struct Matrix{
	ull a[3][3];
	Matrix(){
		a[0][0]=a[0][1]=a[0][2]=
		a[1][0]=a[1][1]=a[1][2]=
		a[2][0]=a[2][1]=a[2][2]=0;
	}
	Matrix operator *(const Matrix&b)const{
		Matrix c;
		c.a[0][0]=(a[0][0]*b.a[0][0]+a[0][1]*b.a[1][0]+a[0][2]*b.a[2][0])%P;
		c.a[0][1]=(a[0][0]*b.a[0][1]+a[0][1]*b.a[1][1]+a[0][2]*b.a[2][1])%P;
		c.a[0][2]=(a[0][0]*b.a[0][2]+a[0][1]*b.a[1][2]+a[0][2]*b.a[2][2])%P;
		c.a[1][0]=(a[1][0]*b.a[0][0]+a[1][1]*b.a[1][0]+a[1][2]*b.a[2][0])%P;
		c.a[1][1]=(a[1][0]*b.a[0][1]+a[1][1]*b.a[1][1]+a[1][2]*b.a[2][1])%P;
		c.a[1][2]=(a[1][0]*b.a[0][2]+a[1][1]*b.a[1][2]+a[1][2]*b.a[2][2])%P;
		c.a[2][0]=(a[2][0]*b.a[0][0]+a[2][1]*b.a[1][0]+a[2][2]*b.a[2][0])%P;
		c.a[2][1]=(a[2][0]*b.a[0][1]+a[2][1]*b.a[1][1]+a[2][2]*b.a[2][1])%P;
		c.a[2][2]=(a[2][0]*b.a[0][2]+a[2][1]*b.a[1][2]+a[2][2]*b.a[2][2])%P;
		return c;
	}
}g[N][20],zero;
ull qpow(ull a,ull b=P-2){
	ull c=1;
	for(;b;b>>=1,a=1ll*a*a%P)
		if(b&1)c=c*a%P;
	return c;
}
int n,q,fa[N][20],dep[N],L[N],R[N],dcnt;
ull a[N],s[N],f[N],val[N],pd[N][20];
vector<int> G[N];
void dfs(int u){
	L[u]=++dcnt;
	val[u]=s[u]*qpow(a[fa[u][0]])%P;
	if(u>2){
		int v=fa[u][0],w=fa[v][0];
		g[u][0].a[0][0]=a[u]*qpow(a[w])%P;
		g[u][0].a[1][0]=s[v]*qpow(a[w])%P;
		g[u][0].a[0][2]=g[u][0].a[1][1]=g[u][0].a[2][2]=1;
		f[u]=a[w]*f[v]%P*qpow(a[w]*f[v]%P+a[u])%P;
		pd[u][0]=P+1-f[u];
	}
	for(int v:G[u])if(fa[u][0]!=v)
		fa[v][0]=u,dep[v]=dep[u]+1,dfs(v);
	R[u]=dcnt;
}
void pre(){
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i<=n;i++)if(fa[i][j-1])
			fa[i][j]=fa[fa[i][j-1]][j-1],
			g[i][j]=g[i][j-1]*g[fa[i][j-1]][j-1],
			pd[i][j]=pd[i][j-1]*pd[fa[i][j-1]][j-1]%P;
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);int d=dep[u]-dep[v];
	for(int i=17;i>=0;--i)if(d&(1<<i))u=fa[u][i];
	if(u==v)return u;
	for(int i=17;i>=0;--i)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
int find(int u,int d){
	d=dep[u]-d;if(d<0)return 0;
	for(int i=17;i>=0;--i)
		if(d&(1<<i))u=fa[u][i];
	return u;
}
void calc(int u,int d,Matrix&res){
	d=dep[u]-d;if(d<0){res=zero;return;}
	for(int i=17;i>=0;--i)
		if(d&(1<<i))res=res*g[u][i],u=fa[u][i];
}
ull calc2(int u,int d){
	d=dep[u]-d;ull res=1;
	for(int i=17;i>=0;--i)
		if(d&(1<<i))res=res*pd[u][i]%P,u=fa[u][i];
	return res;
} 
bool mem2;
int main(){
	cerr<<(&mem1-&mem2)/1024/1024<<endl;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%llu",a+i);
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		G[u].push_back(v);s[u]+=a[v];
		G[v].push_back(u);s[v]+=a[u];
	}
	f[2]=1;dfs(1);pre();
	for(int i=2;i<=n;i++)
		f[i]=f[i]*a[fa[i][0]]%P*qpow(s[i])%P;
	scanf("%d",&q);
	for(int i=1,st,u,v;i<=q;i++){
		scanf("%d%d%d",&st,&u,&v);
		int w=LCA(u,v);ull ans=0,mul=1;
		if(!(L[st]>=L[w]&&L[st]<=R[w]))
			st=LCA(st,w),mul=calc2(w,dep[st]),st=w;
		if(LCA(v,st)!=w)swap(u,v);
		Matrix c;st=LCA(u,st);
		c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[st],c);ans=(ans+P-c.a[0][2])%P;
		c=zero;c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[w],c);ans=(ans+c.a[0][2])%P;
		c=zero;c.a[0][0]=val[u];c.a[0][1]=1;c.a[0][2]=0;
		calc(u,dep[w]+1,c);ull gu=c.a[0][0];
		c=zero;c.a[0][0]=val[v];c.a[0][1]=1;c.a[0][2]=0;
		calc(v,dep[w]+1,c);ull gv=c.a[0][0];
		int x=find(u,dep[w]+1),y=find(v,dep[w]+1);
		ull tmp=1;
		if(x)tmp=(tmp+gu*a[x]%P*qpow(s[w])%P)%P;
		if(y)tmp=(tmp+gv*a[y]%P*qpow(s[w])%P)%P;
		ans=(ans+tmp*qpow(f[w])%P)%P;
		printf("%llu\n",ans*mul%P);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 7ms
memory: 147788kb

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: 7ms
memory: 148340kb

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: 7ms
memory: 147684kb

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: 15ms
memory: 148912kb

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: 7ms
memory: 148552kb

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: 7ms
memory: 148528kb

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: 3ms
memory: 147672kb

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: 11ms
memory: 147192kb

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: 75ms
memory: 146996kb

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: 85ms
memory: 147528kb

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: 79ms
memory: 148212kb

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: 76ms
memory: 148672kb

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: 88ms
memory: 148528kb

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: 85ms
memory: 147776kb

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: 77ms
memory: 148772kb

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: 77ms
memory: 147788kb

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: 80ms
memory: 148240kb

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: 394ms
memory: 187100kb

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: 395ms
memory: 187044kb

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: 390ms
memory: 187036kb

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: 399ms
memory: 187116kb

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: 385ms
memory: 187056kb

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: 407ms
memory: 187024kb

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: 399ms
memory: 187056kb

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: 398ms
memory: 187120kb

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: 394ms
memory: 187044kb

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: 415ms
memory: 187060kb

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: 429ms
memory: 187128kb

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: 421ms
memory: 187028kb

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: 413ms
memory: 187104kb

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: 422ms
memory: 187172kb

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: 432ms
memory: 186996kb

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: 450ms
memory: 187120kb

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: 429ms
memory: 187124kb

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: 434ms
memory: 186988kb

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: 220ms
memory: 178516kb

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: 239ms
memory: 179324kb

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: 257ms
memory: 180084kb

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: 277ms
memory: 180872kb

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: 292ms
memory: 181652kb

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: 315ms
memory: 182340kb

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: 328ms
memory: 183140kb

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: 360ms
memory: 184008kb

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: 360ms
memory: 184816kb

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: 234ms
memory: 178732kb

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: 264ms
memory: 179492kb

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: 289ms
memory: 180436kb

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: 309ms
memory: 181488kb

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: 350ms
memory: 182416kb

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: 343ms
memory: 183252kb

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: 372ms
memory: 184416kb

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: 394ms
memory: 185280kb

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: 397ms
memory: 186144kb

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