QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#259804#5265. Zbożemikefeng100 ✓397ms38692kbC++143.3kb2023-11-21 14:16:262023-11-21 14:16:28

Judging History

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

  • [2023-11-21 14:16:28]
  • 评测
  • 测评结果:100
  • 用时:397ms
  • 内存:38692kb
  • [2023-11-21 14:16:26]
  • 提交

answer

bool M1;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<iomanip>
#include<cassert>
#include<random>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<map>
#include<set>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
//#include<ext/pb_ds/priority_queue.hpp>
#define fi first
#define se second
#define ll long long
#define Vector Point
#define I128 __int128
#define LD long double
#define ull unsigned ll
#define pii pair<ll,int>
#define pb(x) push_back(x)
#define syt cerr<<"sytakioi\n"
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define look_memory cerr<<abs(&M2-&M1)/1024.0/1024<<'\n'
#define rd_i(l,r) uniform_int_distribution<int>(l,r)(rd)
#define rd_r(l,r) uniform_real_distribution<double>(l,r)(rd)
#define look_time cerr<<(clock()-Time)*1.0/CLOCKS_PER_SEC<<'\n'
using namespace std;
//using namespace __gnu_cxx;
mt19937 rd(time(0));
const int N=1e5+5;
int n,k;
ll ans,sum,num;
vector<pii> e[N];
int fa[N],dis[N],dis1[N],siz[N],son[N],id[N],rk[N],top[N],cnt;
inline void dfs(int u,int fath){
	siz[u]=1;
	fa[u]=fath;
	for(pii x:e[u]) if(x.fi!=fath){
		dis[x.fi]=dis[u]+x.se;
		dfs(x.fi,u);
		siz[u]+=siz[x.fi];
		if(siz[x.fi]>siz[son[u]]) son[u]=x.fi;
	}
}
inline void dfs1(int u,int topf){
	id[u]=++cnt;
	rk[cnt]=u;
	top[u]=topf;
	if(son[u]) dfs1(son[u],topf);
	for(pii x:e[u]) if(x.fi!=fa[u]&&x.fi!=son[u]) dfs1(x.fi,x.fi);
}
struct SEG{
	struct tree{ll sum,tag,val;}tr[N<<2];
	#define ls k<<1
	#define rs k<<1|1
	inline void pushup(int k){tr[k].sum=tr[ls].sum+tr[rs].sum;}
	inline void build(int k,int *a,int l=1,int r=n){
		if(l==r) return void(tr[k].val=2*a[rk[l]]);
		int mid=(l+r)>>1;
		build(ls,a,l,mid);build(rs,a,mid+1,r);
		tr[k].val=tr[ls].val+tr[rs].val;
	}
	inline void push(int k,int val){tr[k].sum+=val*tr[k].val;tr[k].tag+=val;}
	inline void pushdown(int k){if(tr[k].tag) push(ls,tr[k].tag),push(rs,tr[k].tag),tr[k].tag=0;}
	inline void add(int k,int l,int r,int l1=1,int r1=n){
		if(l<=l1&&r1<=r) return push(k,1);
		pushdown(k);
		int mid=(l1+r1)>>1;
		if(l<=mid) add(ls,l,r,l1,mid);
		if(mid<r) add(rs,l,r,mid+1,r1);
		pushup(k);
	}
	inline ll query(int k,int l,int r,int l1=1,int r1=n){
		if(l<=l1&&r1<=r) return tr[k].sum;
		pushdown(k);
		int mid=(l1+r1)>>1;ll res=0;
		if(l<=mid) res+=query(ls,l,r,l1,mid);
		if(mid<r) res+=query(rs,l,r,mid+1,r1);
		return res;
	}
}T[2];
inline void add(int x){
	ans+=dis[x]*num+sum;
	sum+=dis[x];++num;
	int u=x;
	while(x){
		ans-=T[0].query(1,id[top[x]],id[x]);
		if(x!=1) ans+=T[1].query(1,top[x]==1?id[son[1]]:id[top[x]],id[x]);
		x=fa[top[x]];
	}
	x=u;
	while(x){
		T[0].add(1,id[top[x]],id[x]);
		T[1].add(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
}
bool M2;
int main(){
	int Time=clock();
	look_memory;
	cin.tie(nullptr)->sync_with_stdio(false);
	cin>>n>>k;
	F(i,1,n-1){
		int u,v,w;cin>>u>>v>>w;
		e[u].emplace_back(v,w);
		e[v].emplace_back(u,w);
	}
	dfs(1,0);dfs1(1,1);
	F(i,1,n) dis1[i]=dis[fa[i]];
	T[0].build(1,dis);T[1].build(1,dis1);
//	F(i,1,n) cout<<dis[i]<<' ';cout<<'\n';
	add(1);
	F(i,1,k){
		int x;cin>>x;add(x);
		cout<<2*ans<<'\n';
	}
	look_time;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 15
Accepted

Test #1:

score: 15
Accepted
time: 2ms
memory: 7332kb

input:

23 9
1 2 1
1 3 1
2 4 1
2 5 1
4 6 1
4 7 1
4 8 1
8 9 1
8 10 1
8 11 1
8 12 1
3 13 1
13 14 1
14 15 1
14 16 1
14 17 1
14 18 1
14 19 1
14 20 1
14 21 1
14 22 1
22 23 5
10
6
12
8
9
2
16
3
23

output:

8
20
38
52
76
104
198
256
450

result:

ok 9 lines

Test #2:

score: 0
Accepted
time: 2ms
memory: 7696kb

input:

21 3
1 2 1
1 3 1
2 4 1
2 5 1
4 6 1
4 7 1
4 8 1
8 9 1
8 10 1
8 11 1
8 12 1
3 13 1
13 14 1
14 15 1
14 16 1
14 17 1
14 18 1
14 19 1
14 20 1
14 21 1
10
16
5

output:

8
32
56

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 7600kb

input:

4 2
1 2 1
2 3 1
3 4 1
3
4

output:

4
12

result:

ok 2 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 6808kb

input:

3000 30
49 2483 36
1916 1877 41
236 1528 36
326 2104 12
2231 640 32
1510 218 10
2925 759 8
2602 1903 34
2996 2021 5
1633 653 10
2775 989 24
1840 1537 36
1122 1083 7
637 2841 12
2412 2133 32
1103 588 36
2033 929 27
1547 639 21
1998 510 34
275 766 16
2532 1869 42
2375 2950 25
2842 383 12
1513 1295 6
2...

output:

2848
7456
13712
22628
36282
47136
59308
72688
93552
108352
123734
147976
162534
182892
204538
228744
256946
301072
346898
376632
411794
470484
511258
550624
592268
651600
688720
755712
810464
876420

result:

ok 30 lines

Test #5:

score: 0
Accepted
time: 1ms
memory: 7456kb

input:

316 315
77 293 7
113 264 28
27 202 29
161 211 46
79 44 34
165 32 31
80 200 47
90 261 17
237 127 27
173 213 12
19 154 13
141 48 6
210 40 46
284 291 41
257 82 20
228 164 41
316 309 15
195 76 33
221 128 35
237 15 37
249 149 8
257 56 13
141 202 50
227 96 13
20 162 17
98 280 40
216 86 27
171 140 25
144 2...

output:

820
4656
9388
15628
22474
29472
36332
45552
56586
70472
81808
94712
108724
120824
138126
154248
184942
202116
218510
240176
261374
294672
330394
357824
398210
426484
452138
490392
525550
563144
591478
631036
670632
719960
755278
790456
825310
865924
930796
979984
1028658
1069060
1111466
1166964
1206...

result:

ok 315 lines

Test #6:

score: 0
Accepted
time: 2ms
memory: 7044kb

input:

1050 95
948 565 7
151 427 45
725 979 43
635 851 19
17 904 38
705 504 13
883 1007 2
865 965 24
142 33 42
548 1042 43
463 20 45
586 565 41
675 678 12
21 27 15
256 663 33
218 338 6
838 423 36
543 734 19
570 908 33
648 870 4
1010 457 31
526 164 48
982 539 48
354 927 10
77 773 7
360 816 47
129 349 43
754...

output:

4966
42104
72662
136392
191330
274140
345740
417340
505166
635752
723636
836448
1226046
1497084
1669996
1832968
2227976
2588544
2800822
3010628
3221184
3797080
4284778
4569108
5014266
5378004
5707072
6164844
6550090
6892828
7451920
7922220
8375426
8794804
9187824
9913816
10331944
11082980
11968762
1...

result:

ok 95 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 7480kb

input:

500 200
175 28 15
28 242 5
252 28 7
447 28 39
393 28 19
28 181 46
28 149 33
144 28 17
399 28 25
28 388 26
28 89 20
28 434 7
28 466 24
414 28 48
500 28 21
223 28 34
450 28 24
28 184 5
378 28 34
15 28 36
28 354 37
141 28 15
28 438 19
281 28 36
28 234 49
299 28 30
28 455 20
28 428 24
28 59 34
473 28 11...

output:

60
292
612
856
1400
1812
2254
3360
4644
5300
6622
8256
9308
11172
12930
14912
16660
19332
21812
23600
26796
28556
30774
34368
37200
40612
44874
46872
50518
54180
57908
62400
66924
70312
73010
76824
79032
83904
88452
93440
97826
102144
108016
112376
119250
123924
129814
132768
136710
143300
149124
15...

result:

ok 200 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 6552kb

input:

301 300
105 220 1
83 155 31
27 301 50
162 60 48
93 96 18
164 163 29
81 238 15
129 106 13
5 232 21
188 186 21
206 183 10
192 82 29
72 175 42
189 63 33
290 170 20
206 145 3
28 50 5
212 23 21
290 140 27
42 264 8
10 294 48
106 268 12
3 155 48
68 69 42
251 13 5
61 16 37
206 57 8
102 180 28
249 152 39
237...

output:

370
1356
2848
4668
6624
9912
13420
15508
20294
25168
32610
39268
45828
51296
60050
67996
76992
84732
97680
108164
118888
130124
142022
154744
165476
185332
202604
219620
236250
251508
266912
282556
298218
318344
337950
360048
379374
399508
424294
445624
463602
482868
506948
528620
560216
586136
6060...

result:

ok 300 lines

Subtask #2:

score: 35
Accepted

Test #9:

score: 35
Accepted
time: 6ms
memory: 11348kb

input:

10000 9999
1 2 15
2 3 84
3 4 28
4 5 31
5 6 80
6 7 48
7 8 69
8 9 83
9 10 89
10 11 24
11 12 18
12 13 73
13 14 22
14 15 15
15 16 10
16 17 33
17 18 12
18 19 22
19 20 77
20 21 59
21 22 6
22 23 51
23 24 70
24 25 27
25 26 28
26 27 34
27 28 51
28 29 26
29 30 100
30 31 79
31 32 30
32 33 88
33 34 94
34 35 65
...

output:

208492
2011668
3029294
4316292
7471762
10206856
13252686
17588796
21025192
25052796
29796050
35163132
39512648
46987528
52062028
57560164
64229258
69917312
77551144
83720988
93248096
100272996
109636532
118025464
128232664
135870024
147348340
155364516
165771674
174109984
182476862
194406788
2037093...

result:

ok 9999 lines

Test #10:

score: 0
Accepted
time: 126ms
memory: 38688kb

input:

100000 99999
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
10 11 1
11 12 1
12 13 1
13 14 1
14 15 1
15 16 1
16 17 1
17 18 1
18 19 1
19 20 1
20 21 1
21 22 1
22 23 1
23 24 1
24 25 1
25 26 1
26 27 1
27 28 1
28 29 1
29 30 1
30 31 1
31 32 1
32 33 1
33 34 1
34 35 1
35 36 1
36 37 1
37 38 1
38 39 1
...

output:

71866
143732
499654
768480
1015518
1440084
1936622
2374896
3086604
3694432
4949068
5979264
6805914
7591780
8716570
9551876
10497456
11456352
12416952
14000952
15122588
17279624
19162198
20452312
22749834
24669700
26072880
27729268
29172006
31578088
33240790
35272708
37172068
39087640
42257822
447680...

result:

ok 99999 lines

Test #11:

score: 0
Accepted
time: 125ms
memory: 38692kb

input:

100000 99990
1 2 931
2 3 998
3 4 952
4 5 965
5 6 901
6 7 963
7 8 974
8 9 966
9 10 983
10 11 949
11 12 923
12 13 957
13 14 999
14 15 912
15 16 940
16 17 925
17 18 905
18 19 911
19 20 949
20 21 972
21 22 998
22 23 991
23 24 927
24 25 934
25 26 981
26 27 937
27 28 966
28 29 949
29 30 923
30 31 931
31 3...

output:

62679702
378162580
607192168
866089228
1152509830
1443933244
1926973002
2370882512
3244198866
3964410532
4738311530
5675777128
6595655592
7430469332
8225105702
9878710536
11086314396
12376402584
13494172530
15044307180
16837973420
18434501252
20029596352
21322311108
23393506796
26102008576
275956593...

result:

ok 99990 lines

Test #12:

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

input:

100000 99999
1 2 991
2 3 636
3 4 666
4 5 520
5 6 120
6 7 892
7 8 451
8 9 385
9 10 363
10 11 592
11 12 529
12 13 707
13 14 628
14 15 263
15 16 508
16 17 126
17 18 413
18 19 286
19 20 99
20 21 191
21 22 256
22 23 311
23 24 534
24 25 201
25 26 146
26 27 906
27 28 140
28 29 257
29 30 989
30 31 376
31 32...

output:

19706874
99175692
168507806
411520256
623343092
808880672
1032227168
1235032432
1632235546
2005350856
2308365858
2681175316
3049291970
3612517584
3994884598
4387657892
4778012508
5258740700
5858263812
6894659512
7798687766
8479237548
9093338862
10032478096
11122141944
11772147416
12766248484
1383489...

result:

ok 99999 lines

Subtask #3:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Test #13:

score: 50
Accepted
time: 223ms
memory: 25412kb

input:

80003 80002
35943 47219 1
38951 66236 1
6321 31819 1
51129 11994 1
31736 79463 1
38540 25857 1
70891 14201 1
75839 51684 1
28072 41654 1
52999 73775 1
6601 20295 1
44632 33637 1
73534 10211 1
40903 10460 1
49217 1179 1
16717 17778 1
47180 46820 1
54815 7405 1
63649 20210 1
66441 67019 1
13880 37573 ...

output:

238
828
1466
2352
4148
5640
8074
10472
12740
15840
18292
21056
23536
27064
31842
35904
40202
44420
48780
54392
61370
68920
74428
79760
84816
90596
97874
108324
115926
122436
130242
139444
149234
161952
173310
183748
194916
206144
214470
227976
242346
258912
269606
279888
292232
301800
314822
327072
...

result:

ok 80002 lines

Test #14:

score: 0
Accepted
time: 190ms
memory: 24428kb

input:

70004 70003
64346 43381 485
24586 47226 143
40639 35963 209
14315 11930 112
329 19648 23
17037 65330 342
45057 47202 124
11978 1057 178
33862 32694 153
40512 4576 81
54310 10371 18
6192 14491 209
2496 3193 337
53125 64544 284
42738 13845 388
19563 35677 278
65914 51260 10
69768 64131 488
19116 58472...

output:

76654
247100
492584
706172
1070312
1398596
1850980
2440816
2898064
3376848
4009618
4811796
5538166
6509388
7223866
7908696
8619198
9495420
11067184
11863628
13088876
14622164
16049044
17318532
18489924
19852972
21601492
22542084
24094596
25822728
27480448
28894196
31429132
34281684
35822990
38333168...

result:

ok 70003 lines

Test #15:

score: 0
Accepted
time: 115ms
memory: 29640kb

input:

75001 75000
53427 8311 379
52291 47368 409
53125 65549 431
67159 65440 341
57100 29939 111
36933 18320 293
34229 9161 391
37061 37547 340
56930 24188 377
55731 4560 384
36247 42211 210
43077 41741 344
68125 39731 372
5892 38007 201
15854 20036 372
15398 60474 238
45679 74177 257
33310 4169 325
25154...

output:

8808816
26107328
42427046
64024392
146692232
181682016
217549088
274605496
400309520
604030784
729048800
812227056
996772812
1243022904
1381825844
1505432164
1628606808
1788004268
2030303642
2325426736
2634659276
2906290612
3146430308
3398540796
3608056314
3862080768
4221665030
4613969084
4880606748...

result:

ok 75000 lines

Test #16:

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

input:

75002 75001
36378 36340 444
56181 36340 405
32557 36340 146
19598 36340 483
36340 5345 434
36340 54771 72
36340 55991 254
36340 54381 55
36340 36061 357
32465 36340 287
36340 72861 220
54426 36340 304
70489 36340 463
36340 69021 499
62033 36340 320
36340 2898 256
64886 36340 429
23081 36340 399
3634...

output:

1390
4136
6906
10496
17010
22824
32718
40464
52524
62100
78232
86472
93964
104216
115470
131488
142120
165708
189734
214920
232554
248776
270986
299904
331850
346476
379728
395976
420268
453240
491598
538752
583308
630224
667730
699912
732378
775428
817206
845440
887896
942228
1007318
1056528
112230...

result:

ok 75001 lines

Test #17:

score: 0
Accepted
time: 300ms
memory: 25996kb

input:

80000 79999
25056 18821 6
76917 39098 55
32482 30547 457
72782 38166 326
49055 74841 46
14941 13032 24
33396 38658 57
35151 50522 221
50585 49288 59
51504 61922 79
64119 34431 20
1719 5512 465
50496 41858 85
18587 38064 17
45271 65207 145
66102 72408 307
48890 3980 133
8684 54016 313
69020 69220 359...

output:

6822
26700
58896
103792
172740
244468
321878
434076
547310
673664
815542
953744
1136930
1318584
1523818
1709304
1932982
2154888
2441772
2666104
2881856
3207112
3523894
3836152
4167024
4517752
4871882
5295784
5659972
6056480
6483272
6885152
7368176
7713800
8209138
8671840
9185776
9718312
10265520
107...

result:

ok 79999 lines

Test #18:

score: 0
Accepted
time: 219ms
memory: 25476kb

input:

79806 79805
79059 10980 96
63213 70160 96
10065 54191 121
71660 40457 48
19520 36013 437
30934 10485 228
78764 35726 25
51637 30011 277
7350 76133 34
44539 15819 354
8573 29460 365
70083 73704 465
44364 7148 308
4757 9557 182
35690 32106 466
2400 433 9
3570 65328 427
36694 53620 136
68584 65035 118
...

output:

851466
2830676
7576808
11927852
17295556
24750652
30887852
43331716
55363670
71071548
88707216
102153724
119319440
133944212
154658546
173179616
197767596
220580696
237049162
252915416
280862230
310652536
332278264
353224884
380613466
418012740
453048148
486015860
521619812
555641208
599977996
64318...

result:

ok 79805 lines

Test #19:

score: 0
Accepted
time: 152ms
memory: 18216kb

input:

65025 65024
11986 31724 370
11344 34736 163
55173 12709 478
49125 27905 300
48921 60374 181
9003 62613 181
55335 9562 131
32143 10526 103
10601 30247 57
50888 4751 492
34404 52422 256
46861 43111 253
7862 40690 322
15398 57984 102
31485 38825 267
3569 16589 484
2407 8241 286
35423 39262 35
17284 326...

output:

822038
2781452
5147392
10296812
15585484
22190548
30274456
38314200
48887732
60111124
73802638
89267012
102404656
119420840
139095982
160849968
183742804
210406128
236513196
260180020
280948964
302341308
328599108
363071600
389571074
410457680
441072646
462087192
497981436
530388724
567621712
593861...

result:

ok 65024 lines

Test #20:

score: 0
Accepted
time: 133ms
memory: 25044kb

input:

79524 79523
1 2 728
2 3 237
3 4 514
4 5 206
5 6 666
6 7 142
7 8 630
8 9 592
9 10 162
10 11 666
11 12 881
12 13 878
13 14 773
14 15 352
15 16 990
16 17 539
17 18 581
18 19 539
19 20 957
20 21 773
21 22 775
22 23 259
23 24 550
24 25 284
25 26 806
26 27 48
27 28 297
28 29 916
29 30 118
30 31 930
31 32 ...

output:

143720
303076
2009770
4440776
6542480
10037404
14032028
18764680
22936644
28072888
32881148
38771764
44660658
50340380
56379420
61533000
69786008
74986628
87819606
94286952
105010452
110770148
119381008
126285608
133600664
141217144
152551068
159664560
176477656
187905636
198837284
209340516
2179733...

result:

ok 79523 lines

Test #21:

score: 0
Accepted
time: 293ms
memory: 26796kb

input:

100000 99999
11109 15512 532
75868 74441 366
78274 86856 674
55532 95765 622
54994 96276 762
73194 37640 302
1137 35954 699
93131 32605 154
61323 38688 505
84948 53928 452
42193 28246 182
74880 79386 899
38730 22315 646
19139 41269 990
18897 11163 774
9183 55921 29
77514 97592 379
28852 91773 720
21...

output:

179050
627160
1206368
2515664
4003370
5325396
6711050
8226536
9719486
12051436
14085102
16764892
20419172
24573444
27804784
31733020
35747520
40817980
45075600
49550728
55772294
61169028
65788068
70654376
76433560
82141056
87720982
93087512
98131898
104811848
111390588
117105108
122616240
128717108
...

result:

ok 99999 lines

Test #22:

score: 0
Accepted
time: 301ms
memory: 26736kb

input:

100000 99990
40853 1384 975
98094 76831 935
49115 75207 926
92117 10773 945
74050 32411 932
94884 69411 972
66127 2563 984
34142 10168 944
14172 8946 951
34376 52014 932
94249 8378 973
76849 74438 918
66446 88514 912
65064 67287 972
56356 68630 953
61121 43150 944
93486 17973 912
96178 63865 984
863...

output:

270224
849228
1858832
3095400
4300884
6163012
8357006
10052920
11824616
13634572
16531066
19798988
23001964
27682088
32168262
37601976
42199204
47859268
53217102
58039572
62598064
69083396
73039392
78410152
83094284
89423864
96694898
105744900
110750296
116397864
121507460
127914904
137439744
146887...

result:

ok 99990 lines

Test #23:

score: 0
Accepted
time: 149ms
memory: 37268kb

input:

100000 99999
38266 73748 185
37095 94260 917
57398 94569 298
93411 83458 911
91831 59402 304
35762 26671 596
82451 23614 409
803 69556 351
52685 22577 240
90559 80683 218
56850 25115 289
71873 91758 748
54352 36144 369
78525 62086 86
5174 69100 431
10918 60003 430
33342 46393 748
59765 39430 991
603...

output:

55447258
142023620
224427434
338778796
492779310
688983872
907371940
1089453488
1294547862
1601015896
1913444522
2184315208
2709559848
3158698352
3488321018
3836555552
4632611246
5512255196
6159815932
6645493100
7215816050
7718146756
8697506212
9548666088
10138899124
10904589080
11607561530
12362222...

result:

ok 99999 lines

Test #24:

score: 0
Accepted
time: 151ms
memory: 35372kb

input:

100000 99999
65823 91228 697
46420 97434 227
79167 61860 967
11219 3969 796
87852 81737 559
83362 38549 70
48764 19526 397
79515 71845 234
79079 33946 325
97216 39765 667
90920 65236 752
78491 57226 169
98219 66591 370
15882 37736 853
50719 22144 292
94542 53588 124
68769 58666 506
59099 63620 879
5...

output:

11600814
88341032
142309680
346388796
550470630
729817668
902694660
1207522256
1430758076
1700973280
2082247170
2399601044
2693332110
3017933620
3340736476
3686398384
4116501860
4484894284
5078703974
5785977580
6297584320
6765331956
7284572630
7750565864
8848556696
9358543480
10399228054
10951021784...

result:

ok 99999 lines

Test #25:

score: 0
Accepted
time: 137ms
memory: 25436kb

input:

100000 99999
19094 98979 542
98979 74454 748
35832 98979 690
98979 27153 605
38499 98979 621
49529 98979 956
30990 98979 107
20799 98979 961
98979 94140 997
14820 98979 727
67085 98979 941
77460 98979 591
98979 65899 127
57549 98979 136
98979 73037 959
11946 98979 391
98979 48821 613
98979 3507 652
...

output:

2092
6240
11964
21072
33050
45696
64792
80864
102384
115020
148170
182688
216788
247884
293280
331616
355980
404892
458660
519040
568050
636416
680616
736176
786600
822536
872316
907368
990408
1038960
1090022
1147200
1245090
1289892
1353100
1394784
1441076
1494692
1576068
1679280
1773250
1888656
197...

result:

ok 99999 lines

Test #26:

score: 0
Accepted
time: 141ms
memory: 25960kb

input:

100000 99999
53742 27926 174
53742 56430 970
64423 53742 107
45612 53742 410
98835 75859 123
53742 63010 783
53742 15109 114
70191 53742 152
53742 48055 762
41587 86214 54
53742 87517 538
53742 43839 952
53742 50071 881
92010 53742 198
53742 77637 940
53742 14343 947
58550 53742 899
96129 53742 908
...

output:

1190
6800
15780
23344
36090
46848
66276
77312
102870
115500
142604
159096
173914
197624
237810
280640
299676
346104
377188
407040
441672
495528
537648
599184
663800
755820
786996
842744
910252
969120
1035772
1123072
1170642
1266364
1352820
1422072
1481406
1594784
1677936
1794560
1866812
1941156
2039...

result:

ok 99999 lines

Test #27:

score: 0
Accepted
time: 397ms
memory: 27380kb

input:

100000 99999
63458 74251 390
8 90321 502
80891 56160 136
72675 35048 804
4269 56499 87
82070 77183 335
59493 75600 839
55277 6214 782
91353 54667 343
90754 87198 715
55502 57716 478
89654 30724 328
87180 16205 768
89169 14108 440
14220 86244 608
75438 21995 562
98943 7911 487
12845 34767 988
38245 1...

output:

12630
55992
123520
213836
341430
488156
657996
830236
1058932
1313060
1589698
1882032
2158768
2521444
2852006
3234216
3561876
3975320
4428202
4906580
5418482
5876072
6411370
7047460
7732228
8391480
9077890
9791944
10581986
11258160
12179800
13035832
13876028
14791060
15735906
16694852
17539530
18352...

result:

ok 99999 lines

Test #28:

score: 0
Accepted
time: 271ms
memory: 27024kb

input:

99856 99855
18397 64992 7
74004 93185 433
1271 40973 754
64407 84732 792
43476 6649 570
20618 74851 331
61920 31118 679
11319 39031 569
8885 2564 429
60680 31923 959
75670 71183 256
13660 4335 504
70888 8085 406
28072 83962 55
14265 56888 104
65437 36203 392
66039 20252 983
9422 98576 85
85480 722 4...

output:

2035684
4752920
11761442
17861552
31799150
45096712
59768204
76499332
99361260
132508112
164355212
185178972
205634870
228101296
262211028
300509752
351196718
396337892
457499560
516678584
582902264
632751860
705864084
781468232
856466854
925869848
1017858080
1094995292
1164968158
1249125352
1357984...

result:

ok 99855 lines

Test #29:

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

input:

100000 99999
1 2 398
2 3 722
3 4 452
4 5 393
5 6 81
6 7 678
7 8 761
8 9 869
9 10 294
10 11 228
11 12 710
12 13 415
13 14 853
14 15 173
15 16 533
16 17 9
17 18 178
18 19 521
19 20 850
20 21 58
21 22 999
22 23 156
23 24 726
24 25 203
25 26 774
26 27 665
27 28 362
28 29 340
29 30 103
30 31 101
31 32 19...

output:

35330418
70660836
179246166
312418864
436919240
587040272
779446068
948570552
1119242500
1321770908
2034016024
2283486376
2690271086
2967838912
3473510956
4363049784
4728578444
5761459668
6514514520
6974112664
7811250242
9061463396
9638254050
10314894508
10895580728
11808198384
12800140522
142105773...

result:

ok 99999 lines

Test #30:

score: 0
Accepted
time: 166ms
memory: 26208kb

input:

99856 99855
1 2 846
2 3 292
3 4 240
4 5 823
5 6 669
6 7 482
7 8 454
8 9 297
9 10 14
10 11 964
11 12 186
12 13 472
13 14 678
14 15 405
15 16 451
16 17 464
17 18 833
18 19 962
19 20 33
20 21 271
21 22 371
22 23 609
23 24 308
24 25 767
25 26 6
26 27 27
27 28 804
28 29 392
29 30 537
30 31 98
31 32 228
3...

output:

207842
811144
2795858
4401344
6674796
8915504
13135142
15294940
20077276
22568836
27451440
31968336
38578940
46146656
54611758
64334392
73089754
82728340
93482924
102218264
111081272
125276548
136498202
145886464
159056158
169754612
178590286
190280828
202843508
211838092
225437126
243512148
2637901...

result:

ok 99855 lines

Extra Test:

score: 0
Extra Test Passed