QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#413888#5148. Tree DistanceFAKUMARERAC ✓1627ms154124kbC++144.0kb2024-05-18 11:26:142024-05-18 11:26:15

Judging History

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

  • [2024-05-18 11:26:15]
  • 评测
  • 测评结果:AC
  • 用时:1627ms
  • 内存:154124kb
  • [2024-05-18 11:26:14]
  • 提交

answer

#include <bits/stdc++.h>

const int MAXN = 1000005;
const int MAXM = 1000005;

using namespace std;

struct Edge {
	int to, nxt, w;
} E[MAXN << 1];

int H[MAXN], F[MAXN], tot;

inline void Add_Edge (const int u, const int v, const int w) {
	E[++ tot] = {v, H[u], w}, H[u] = tot;
	E[++ tot] = {u, H[v], w}, H[v] = tot;
}

bool Vis[MAXN];
int Siz[MAXN], Max[MAXN];
long long Ans[MAXN];
int rt, Now;

inline void DFS1 (const int x, const int f) {
	Siz[x] = 1, Max[x] = 0;
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f && !Vis[E[i].to])
			DFS1 (E[i].to, x), Siz[x] += Siz[E[i].to], Max[x] = max (Max[x], Siz[E[i].to]);
	Max[x] = max (Max[x], Now - Siz[x]);
	if (Max[x] < Max[rt] || !rt) rt = x;
}

struct Node {
	int x;
	long long dis;
	
	inline bool operator < (const Node &a) const {
		return x < a.x;
	}
};

struct Ques {
	int l, id;
};

vector <int > P[MAXN];
vector <Ques> I[MAXN];
vector <Node> S;

inline void DFS2 (const int x, const int f, const long long dis) {
	S.push_back ({x, dis});
	for (int i = H[x]; i; i = E[i].nxt) 
		if (E[i].to != f && !Vis[E[i].to])
			DFS2 (E[i].to, x, dis + E[i].w);
}

Node Stack[MAXN];
int top = 0;

inline void DFS3 (const int x, const int f) {
	Vis[x] = 1, S.clear ();
	// for (int i = H[x]; i; i = E[i].nxt)
		// if (E[i].to != f && !Vis[E[i].to])
	DFS2 (x, f, 0);
	
	sort (S.begin (), S.end ()), top = 0;
	
	for (int i = 0; i < (int) S.size (); ++ i) {
		while (top && S[i].dis <= Stack[top].dis) -- top;
		if (top) P[S[i].x].push_back (Stack[top].x);
		Stack[++ top] = S[i];
	}
	
	top = 0;
	
	for (int i = (int) S.size () - 1;  ~ i; -- i) {
		while (top && S[i].dis <= Stack[top].dis) -- top;
		if (top) P[Stack[top].x].push_back (S[i].x);
		Stack[++ top] = S[i];
	}
	
	for (int i = H[x]; i; i = E[i].nxt)
		if (E[i].to != f && !Vis[E[i].to])
			Now = Siz[E[i].to], rt = 0, DFS1 (E[i].to, x), DFS3 (rt, x);
}

int N, Q;
int u, v, w;

namespace Tree_Cut {
	int Son[MAXN], Top[MAXN], Dep[MAXN];
	long long Dis[MAXM];
	
	inline void DFS_1 (const int x, const int f, const long long dis = 0) {
		Dep[x] = Dep[F[x] = f] + 1, Siz[x] = 1, Dis[x] = dis;
		for (int i = H[x]; i; i = E[i].nxt)
			if (E[i].to != f)
				DFS_1 (E[i].to, x, dis + E[i].w), Siz[x] += Siz[E[i].to], Siz[E[i].to] > Siz[Son[x]] ? Son[x] = E[i].to : Son[x];
	}
	
	inline void DFS_2 (const int x, const int top) {
		Top[x] = top;
		if (Son[x]) DFS_2 (Son[x], top);
		for (int i = H[x]; i; i = E[i].nxt)
			if (E[i].to != F[x] && E[i].to != Son[x])
				DFS_2 (E[i].to, E[i].to);
	}
	
	inline int LCA (int u, int v) {
		while (Top[u] != Top[v])
			Dep[Top[u]] > Dep[Top[v]] ? u = F[Top[u]] : v = F[Top[v]];
		return Dep[u] > Dep[v] ? v : u; 
	}
	
	
	inline long long GetDis (const int u, const int v) {
		return Dis[u] + Dis[v] - (Dis[LCA (u, v)] << 1);
	}
}

namespace BIT {
	long long T[MAXN];
	
	#define lowbit(x) (x & -x)
	
	inline void Build () {
		memset (T, 127, sizeof T);
	}
	
	inline void Add (int x, const long long v) {
		while (x) T[x] = min (T[x], v), x -= lowbit (x); 
	}
	
	inline long long Que (int x) {
		long long Ret = (1ll << 62);
		while (x <= N) Ret = min (Ret, T[x]), x += lowbit (x);
		return Ret;
	}
}

using namespace Tree_Cut;

int main () {
	
	cin >> N, Now = N;
	
	for (int i = 2; i <= N; ++ i)
		cin >> u >> v >> w, Add_Edge (u, v, w);
		
	DFS1 (1, 0), DFS3 (1, 0);
	
	DFS_1 (1, 0), DFS_2 (1, 1);
	
//	cerr << "N = " << N << '\n';
	
//	for (int i = 1; i <= N; ++ i) {
//		cerr << "R = " << i << '\n';
//		for (auto p : P[i]) cerr << "L = " << p << ", Dis = " << GetDis (p, i) << '\n';
//	}
	
	cin >> Q, BIT::Build ();
	
	for (int i = 1; i <= Q; ++ i)
		cin >> u >> v, I[v].push_back ({u, i});
	
	for (int i = 1; i <= N; ++ i) {
		for (auto p : P[i]) if (p != i) BIT::Add (p, GetDis (i, p));
		for (auto p : I[i]) Ans[p.id] = BIT::Que (p.l);
	}
	
	for (int i = 1; i <= Q; ++ i)	
		cout << (Ans[i] == (1ll << 62) ? -1 : Ans[i]) << '\n';
	
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 70900kb

input:

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

output:

-1
3
7
7
2

result:

ok 5 number(s): "-1 3 7 7 2"

Test #2:

score: 0
Accepted
time: 1627ms
memory: 145268kb

input:

199999
31581 23211 322548833
176307 196803 690953895
34430 82902 340232856
36716 77480 466375266
7512 88480 197594480
95680 61864 679567992
19572 14126 599247796
188006 110716 817477802
160165 184035 722372640
23173 188594 490365246
54801 56250 304741654
10103 45884 643490340
127469 154479 214399361...

output:

29573323
1178569098929
4088
65959
4366
7019193245
760172089
4867978
328055210
55721881562
2062364707
339719
92126
92126
4366
138216269
8212187
9404444928
2681285
4366
710854
114886
65959
1818252547
92126
91087
8367049186
26776689
5718199
710854
92126
1162886184
365255209
92126
710854
92126
710854
43...

result:

ok 999999 numbers

Test #3:

score: 0
Accepted
time: 1516ms
memory: 147528kb

input:

199999
190688 126676 336782051
151926 172504 967158526
143443 156079 327684610
1651 1650 636911896
126737 133579 99211799
51923 27823 578381240
143114 144835 986461144
174389 157101 166893672
155523 184758 123327399
156455 189770 534771115
153509 197636 266156555
152671 90015 599111256
22725 89687 5...

output:

29833168
264977
1644455
256572
20118223
2389018
282587
39463809
12875907
137469
361698
1255777
264977
212187
746769804
1930627
752241
2970313
10614966565
22687
266502970
361698
21800926214
1431959
54685
451573
451573
54685
187821
725293
429916
183648
704808
22687
22687
300462283
403282864
4400484
12...

result:

ok 999998 numbers

Test #4:

score: 0
Accepted
time: 1501ms
memory: 132876kb

input:

199995
153159 165760 776455627
70942 92810 701471078
99219 55616 414591262
121378 184571 934631873
166947 139904 743113587
79389 78273 319784778
52291 18432 252252592
88548 55574 54549492
11451 152159 217228873
18236 26964 668737868
107402 155790 854680897
164320 169293 481056083
147736 16503 125677...

output:

876734
617283472
2956724
273071
607768140
7547720129
1968705652
2956724
2336206
14076
876734
42655
99169
20057482
99466244
14076
383075
14076
14076
4606137
360556692
14076
2336206
52653
4321345839
105208174
232513
111656
232513
277017
96029
1471103
383075
253372538
896912412
491803653
255375068
-1
1...

result:

ok 999998 numbers

Test #5:

score: 0
Accepted
time: 1483ms
memory: 134880kb

input:

199995
98127 183840 947466137
131770 43169 867336904
170663 16213 899594096
141858 34108 869164504
98128 7446 947922880
105351 81980 962423467
76842 185730 944927309
177512 115765 941062577
156944 13505 788909554
96758 65903 850126278
163293 57905 959251199
11053 95537 845878127
31894 111163 9797415...

output:

785448841
785343265
785343265
785343265
785343265
785592131
785864325
785358155
785781452
785367806
785476787
785343381
785382148
785350742
815114036
785350742
785352925
786524136
786184239
789438475
785382148
789006316
786071540
785350742
785343265
785957219
785382148
786071540
785448841
785350742
...

result:

ok 999997 numbers

Test #6:

score: 0
Accepted
time: 1561ms
memory: 140872kb

input:

199995
188737 188710 657768451
123356 136732 18065996
125671 161064 244754808
9700 148067 278208202
10602 92611 595505217
29002 87205 380484379
117306 163318 928372257
153163 171288 82918152
150883 116821 91763948
157643 88748 507921240
84580 50418 768981233
129701 135932 640672893
76478 178376 6130...

output:

365757
153622
44451
8361969
5402084
5402084
2780170
52603500163
28151680
14852622302
339653802
237414
25917285
604333
7253185
150742
657635
281397
104252
91299921657
126474
153622
585585
2097522188
365757
35017603
25917285
93979475
30571
249518
61323423
9083750407
7253185
153622
104252
30571
4393285...

result:

ok 999998 numbers

Test #7:

score: 0
Accepted
time: 1477ms
memory: 143128kb

input:

199997
19834 19835 971754151
185536 55509 828706415
59191 34958 883955257
46270 99816 995864680
3549 3548 992149860
43671 83307 971273790
94791 108996 983559363
48289 154236 886619840
179148 130746 843045643
15416 15415 809129017
48293 68983 804210045
7254 7253 876811892
123012 143419 984989534
8431...

output:

2849582455
78181350350
5157305864
138375179593
801862614
801777140
810640396
802820979
801787993
282930525493
1723759410
455994735849
1693341930
801916439
801777109
803256302
801777109
863007526
802728031
-1
801810913
803425621
801787799
801792593
919030630
801778642
801862614
17023522379
801813075
...

result:

ok 999997 numbers

Test #8:

score: 0
Accepted
time: 1369ms
memory: 134912kb

input:

200000
136719 136720 915403261
24341 24342 918039468
3513 3512 909298912
181355 181356 849066963
174352 174353 834646994
176495 176494 955191871
128059 164853 918344653
148921 148920 896143929
167949 75144 919725537
60837 41169 935167113
17649 1047 974096195
160355 160354 799041904
42518 50812 86590...

output:

784050284
784050685
-1
784051430
784070725
784281470
784284703
784120368
784547627
-1
785073476
787549031
784055128
784463706
784050685
784073039
784284703
784052946
786803807
784079973
784051430
784050685
784050685
784083819
784123411
784052810
784050284
784051430
790502842
784073039
792457189
7841...

result:

ok 1000000 numbers

Test #9:

score: 0
Accepted
time: 1579ms
memory: 139136kb

input:

199995
142018 181514 536917111
144429 164010 780287647
179084 32833 782765941
188039 109798 780410499
126524 152824 660225535
157422 132475 564275297
83816 109659 814095889
85992 15169 952763393
197908 11617 364598459
49933 65150 447412103
73029 73529 924773983
99193 199821 733469456
98037 83515 513...

output:

335396803
335292833
451105110
334134527
363624130
347047212
334163469
334267746
334174940
339884459
334228035
334267746
334134527
338138027
462248469
2311321210
834894569
334160954
334163469
334160954
334134527
334134527
360231505
334160954
415635752
334174940
32628105033
5097623607
334160954
334380...

result:

ok 999996 numbers

Test #10:

score: 0
Accepted
time: 1325ms
memory: 147088kb

input:

200000
190520 22456 884507444
83541 65208 848177231
16273 76597 906554365
35271 35272 848759280
106514 106513 850702640
70129 70130 908024857
188573 188574 896855798
86950 77353 966829342
964 963 993031740
23731 23732 912301150
64903 64902 936675879
79521 79520 990544440
27473 27474 984602192
4338 4...

output:

845979429
845972365
846401568
846003928
845976608
845971901
859177646
845972365
847146665
845972365
845974937
845971901
846941448
846063153
845983404
845972365
845975284
846066338
845974937
845972365
845972885
845972365
845972365
845972365
845981769
845974937
852785925
845972885
846096781
845981949
...

result:

ok 1000000 numbers

Test #11:

score: 0
Accepted
time: 1448ms
memory: 149880kb

input:

199997
198958 123433 872995348
182737 14744 105372589
115892 154664 748438106
152992 191558 934482928
129047 41622 298087993
119522 99306 968360337
97554 125132 408995773
23983 23982 431636307
11514 11513 252372273
74 75 151324915
104906 140704 819229459
19824 19825 771010696
113634 119021 860232699...

output:

6559734
44352
-1
715970280
4028144
273760525
1472815
167852
282004198
1664762995
21380
53339
16116197516
2270
360999229
783272
588675209
24858422
10421544
21380
21380
19577
21380
2270
223989
2546527
28765
2270
2139075
779582
1149668501
2270
152586
1539405854
2270
1051602999
4897937046
21380
1976936
...

result:

ok 999998 numbers

Test #12:

score: 0
Accepted
time: 1316ms
memory: 144012kb

input:

199998
169275 169276 363993247
170909 170910 856125415
49492 23499 864613900
166959 124838 984373255
108425 108426 661474407
128148 7119 757725985
156806 187750 679889223
57854 82549 813297908
57463 57464 830647792
104803 28472 684518693
54379 54378 334779523
133964 133965 873281191
123987 123986 42...

output:

298601918
298600335
298601918
298603383
298600335
298843695
298601918
298600335
298600335
298602966
298643513
298724545
298600335
298903953
298600335
298600335
298600335
298590317
298590999
298903953
298736056
298601918
298600335
-1
298601918
298643513
298590317
298595437
298610341
298643513
2986019...

result:

ok 999999 numbers

Test #13:

score: 0
Accepted
time: 1508ms
memory: 143828kb

input:

199995
191403 98023 716463764
197192 178951 588532401
82115 106914 722300235
29381 85640 806273337
174167 79660 566080922
161039 137713 736161110
77279 134893 704431557
40435 78681 854039744
70029 197022 983096190
31971 110535 928486081
103665 169579 988711938
30998 122617 660249278
54052 115843 528...

output:

491076289
508488954
491113927
491070059
491155663
1365312298
491076289
491113927
491074169
511083861
491709966
491134568
491076289
493243808
491108579
491134966
495382453
491070059
550063234
491074416
492119807
556534357
491074169
491227124
491808244
491681351
572261539
491074416
491134568
491070059...

result:

ok 999997 numbers

Test #14:

score: 0
Accepted
time: 1538ms
memory: 138032kb

input:

199997
189231 191069 222603311
22772 50338 528975060
4414 176656 770872782
76293 187071 179840949
104294 178484 451737458
143517 149584 327704915
45962 82918 789360832
15981 78852 160047704
108823 164541 866935826
4210 143647 345986719
20044 135473 556204754
128988 55300 462602710
16236 138363 53286...

output:

123574081
129668249
122477884
121798356
130749553
121798356
666297511
122390636
123279193
121798356
157934589
122073147
121827208
153756275
1847731334
121995690
121798356
121827208
51482219455
14242566401
124457634
122262015
123574081
9670789461
139213551
25889844426
245623624
122262015
121859520
23...

result:

ok 999995 numbers

Test #15:

score: 0
Accepted
time: 1465ms
memory: 142168kb

input:

199997
196729 178443 822652784
37684 78736 961577572
71546 71179 83113125
70876 170948 619898332
195216 141322 695695729
7343 7342 522582037
64972 100917 200100774
139332 66653 738906762
72764 96515 698111696
76261 57636 406407126
166856 101582 396561592
119251 134863 529752870
41751 124423 20798792...

output:

11747759
171328
129871
58666
11349386
14967
-1
14967
50238
37237
2952252
4916078
58666
41129471
213211
46793
35599644
35599644
37237
118450
49841
7321769
14967
58666
7229082
213211
2463014
129871
48000
479541
14967
14967
129871
2463014
48000
190208
7229082
58666
2792241
427172
1344099
14967
92067
46...

result:

ok 999998 numbers

Test #16:

score: 0
Accepted
time: 1122ms
memory: 135652kb

input:

200000
153782 153783 769086740
12534 12535 598518556
119800 119801 659189138
122107 122106 804974462
134565 134566 982665716
37426 37425 806563655
141084 141085 674901606
15594 15595 843395699
143263 143264 884503286
45529 45530 630485548
110958 110957 727790548
27951 27950 892818177
37868 37869 979...

output:

588545783
588734744
588548943
588546547
588615931
589153053
591212347
589505146
588545783
588640240
588549191
588689013
588615931
588545783
588577594
588596827
588548943
588877817
588546547
588545783
592272746
588545783
588545783
588883601
588545783
589014157
588566343
588548943
588546547
588548943
...

result:

ok 1000000 numbers

Test #17:

score: 0
Accepted
time: 1467ms
memory: 145184kb

input:

200000
26456 172034 340953865
35764 89560 213052297
189363 81074 905753856
52429 70924 399851170
126019 135414 642908576
45574 147767 611706240
153915 65139 446294986
87198 25414 617992596
147037 127211 702153711
58955 48053 17801416
3240 81300 939004190
12077 12078 922600659
168498 191965 79103871
...

output:

8913
2703482
491502
744
513814
34899
61716
5596
90574
9456
1543374
619510
9456
80782
275863
144725
61716
144725
5596
144725
90574
135118
9456
293468
144725
5596
9456
469540
9456
144725
144725
80782
5596
6497792
8913
144725
5596
80782
744
5596
2190850
135118
61716
563620478
9456
144725
1556920
9456
-...

result:

ok 1000000 numbers

Test #18:

score: 0
Accepted
time: 1361ms
memory: 149772kb

input:

200000
7328 7327 576614606
79065 79066 400194214
164865 186187 705600002
115859 103495 466149546
164679 164678 292434872
44403 107541 757404035
157272 139078 970983397
43405 43406 649921531
60980 199029 985527118
95604 113723 248134432
71896 77341 342210685
169451 169450 564969266
91752 91751 807260...

output:

217377228
217888645
218356473
219239500
217311001
217311001
217437715
217311001
217888009
217311001
217315358
221292288
217318303
217888645
217385915
217311001
217318303
217377228
217964399
217311001
350204278
281814025
217405921
220756020
217315358
217688648
217318303
217311001
217888009
217517218
...

result:

ok 1000000 numbers

Test #19:

score: 0
Accepted
time: 1493ms
memory: 141744kb

input:

199995
67016 14947 103915999
186745 103204 126650538
190376 155808 418126023
11798 76373 416135572
189779 112130 855103408
4492 4491 728054221
97263 122412 23265829
55778 41531 706426834
99858 55402 433650633
24496 139382 867002607
137624 27430 974365345
99542 6067 719252450
49575 9882 370978848
119...

output:

6973740
51712
51712
32518
16117
1232327
16117
32518
155122
16117
15758
16117
51712
16117
206571
719159
16117
16117
254420
51712
16117
155122
51712
16117
6224068
16117
51712
6885855430
2214239
32518
254901
16117
308659
16117
991659
16117
16117
2445241
1697579
1668432
280720
148503632
6796013
16117
16...

result:

ok 999997 numbers

Test #20:

score: 0
Accepted
time: 1493ms
memory: 141608kb

input:

200000
16651 16652 505820240
147676 82821 570330701
161547 47896 352665577
1364 152717 537185634
60059 65068 326011970
5256 5257 525378285
190492 141013 426515131
105281 89030 725929009
9551 9552 45294903
360 128350 40437550
118821 33676 237404541
176299 105973 113294494
25967 170139 240927064
10904...

output:

12917331
1342035558
8039
683830
58493
664326
8039
16689105610
12595
8039
21120
41159
1919652538
40626
36158
40626
21120
40626
-1
781215
5272859667
112922
12595
1047014
36158
36158
121402
1578681494
1224730772
1480008
982601279
8039
1612402
40626
461033135
21120
112922
12595
8039
3806840186
256337019...

result:

ok 1000000 numbers

Test #21:

score: 0
Accepted
time: 1072ms
memory: 131400kb

input:

199995
11339 11338 477628317
46210 46209 864760526
152796 152797 773264940
153808 153807 630955730
124599 124600 444496156
1280 1281 876831442
130109 130110 814233413
15838 15839 591724113
153636 153635 427444100
195377 195376 418941114
44026 44025 644905153
95109 95110 976732072
19102 19103 3414576...

output:

301039883
301118147
300865061
301205929
301014172
300864802
300862566
305298569
300862566
301108459
301039883
300893132
301064086
300970645
301581793
300864992
462014789
300935197
302612899
300864802
301050309
323771590
300864802
300897033
303849669
300864802
300897033
300864992
300865061
300990530
...

result:

ok 999999 numbers

Test #22:

score: 0
Accepted
time: 1349ms
memory: 150836kb

input:

200000
45920 45918 666922538
140074 189761 925250413
81837 81838 456283736
138825 141009 723459952
9091 9093 681677835
133536 157733 572162743
180645 198609 596267814
100663 167214 157356603
161934 99602 184989261
76951 76950 773852155
52716 52713 939742933
20436 20437 391690137
18186 18187 20629078...

output:

111418468
110670253
110812998
110670253
110670253
111451417
110677354
113989122
110670253
110670253
2531919705
110678363
110832934
110689186
110830888
17619576541
110689186
111451417
162119573
110689186
111809082
110689186
110689186
119339801
114980169
114980169
110689186
120797794
110672870
1117750...

result:

ok 1000000 numbers

Test #23:

score: 0
Accepted
time: 1364ms
memory: 154124kb

input:

199998
185738 148392 980494489
150264 111676 303645309
172460 125497 657877770
116731 159817 514827526
46908 46909 827687238
186013 131893 426576290
36454 36452 473474452
103412 94994 33300602
93804 142720 432794929
68899 68900 483223763
115311 92040 730353673
1686 1685 257847877
68640 68641 2117693...

output:

18047933
20743
20743
6411
219163
34479435367
89738
74819
622650
48899742812
1437273
6411
3142
3142
247112
2809047
20743
2814043
1265827
4577843442
182837
189830
163357
6411
5885910
74819
20743
318428404
307966
20743
1753818
6411
622650
3142
-1
1753818
3771755
3142
20743
33215317
1502489
219163
40797...

result:

ok 999999 numbers

Test #24:

score: 0
Accepted
time: 1192ms
memory: 146984kb

input:

200000
27899 27897 857984358
8957 8958 556964444
182332 163704 951022981
32234 32235 256381691
43737 43735 179255650
54901 54904 843000476
195107 164783 682658146
118275 118274 131715746
127980 127982 355602506
137671 137673 740375866
169681 162109 337665326
20815 20813 567918180
81740 81741 3608198...

output:

178148780
102669224
115691657
2643643879
101344814
101317414
102466341
106440018
101381027
101263252
101317414
103395313
101292784
102013012
640977463
104054035
167220263
101292784
113191575
1304661536
101253671
113703550
101334973
101315405
101292784
101334973
101401996
102406335
101292784
10131741...

result:

ok 1000000 numbers

Test #25:

score: 0
Accepted
time: 1167ms
memory: 150924kb

input:

199999
73077 73078 265745062
94069 94070 785726530
94582 94584 881276992
103185 103184 93678657
14589 14588 136123419
180476 184861 907316741
76629 76628 133273848
51978 51977 874153740
98665 98663 820756619
175757 163338 683612839
82841 82840 591389788
60212 60211 129437172
40329 40328 548764998
20...

output:

17495
13115
28147
227547
17495
28147
60503
37915
17495
189284
68174
19783
2024586
68174
28889
6482221
2073137
253118
125527
8403930
120710
17495
288425
1533525
19783
28889
562186
8112003
28147
68174
17495
10178143
1669819
28147
-1
2024586
239026218
1106359
17495
28147
28147
103124
28147
13115
120786...

result:

ok 999996 numbers

Test #26:

score: 0
Accepted
time: 1130ms
memory: 146028kb

input:

199996
198407 198408 977903422
178106 178105 992188243
45567 45569 933587561
11371 11373 801169825
60947 60939 825266334
177849 177851 820614996
145437 145438 843822287
134388 134389 878328589
13705 13708 853806827
82472 82471 888716551
178466 178467 927446838
120100 120097 906952923
140153 140155 8...

output:

797146666
797416845
797146666
797139594
797148024
797148024
797147409
797139594
797147409
797139594
797145314
797143173
797148024
797139594
797146666
797147409
797146666
797139594
797139594
797145314
797150588
797146666
797145314
797139594
797146666
797162375
797139594
797162375
797148930
797139594
...

result:

ok 999996 numbers