QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#34313#246. 通道Qingyu100 ✓1742ms75960kbC++236.2kb2022-06-06 23:38:222022-06-06 23:38:23

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-06-06 23:38:23]
  • 评测
  • 测评结果:100
  • 用时:1742ms
  • 内存:75960kb
  • [2022-06-06 23:38:22]
  • 提交

answer

#include <bits/stdc++.h>

const int N = 1e5 + 50;

struct tree_t {
	int fa[N], dep[N], dfn[N], low[N], siz[N], son[N], top[N];
	int64_t dsum[N];
	std::vector<std::pair<int, int64_t>> adj[N];
	int tot;
	tree_t() {
		tot = 0;
	}
	void add_edge(int x, int y, int64_t w) {
		adj[x].emplace_back(y, w);
		adj[y].emplace_back(x, w);
	}
	
	void dfs1(int x, int f, int d, int64_t dis) {
		siz[x] = 1;
		dep[x] = d;
		dsum[x] = dis;
		fa[x] = f;
		int max_son = -1;
		for (auto [y, w] : adj[x])
			if (y != f) {
				dfs1(y, x, d + 1, dis + w);
				siz[x] += siz[y];
				if (max_son < siz[y]) {
					max_son = siz[y];
					son[x] = y;
				}
			}
	}
	void dfs2(int x, int topf) {
		dfn[x] = ++tot, top[x] = topf;
		if (son[x]) {
			dfs2(son[x], topf);
			for (auto [y, w] : adj[x])
				if (y != fa[x] && y != son[x])
					dfs2(y, y);
		}
	}
	bool is_ancestor(int x, int y) const { // check if x is the ancestor of y
		return dfn[x] <= dfn[y] && dfn[y] < dfn[x] + siz[x];
	}
	int LCA(int x, int y) const {
		while (top[x] != top[y]) {
			if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
			x = fa[top[x]];
		}
		return dep[x] < dep[y] ? x : y;
	}
	int64_t dist(int x, int y) const {
		int g = LCA(x, y);
		return dsum[x] + dsum[y] - 2 * dsum[g];
	}
	void init() {
		dfs1(1, 0, 1, 0);
		dfs2(1, 0);
	}
} T[3];

bool ban[N];
int col[N];
int64_t ans, d0[N];
int get_size(int x, int fa = -1) {
	int siz = 1;
	for (auto [y, w] : T[0].adj[x])
		if (y != fa && !ban[y])
			siz += get_size(y, x);
	return siz;
}
int get_centroid(int x, int tot, int fa = -1) {
	int mx = 0, siz = 1;
	for (auto [y, w] : T[0].adj[x])
		if (y != fa && !ban[y]) {
			int p = get_centroid(y, tot, x);
			if (p > 0) return p;
			mx = std::max(mx, -p);
			siz -= p;
		}
	mx = std::max(mx, tot - siz);
	if (mx * 2 <= tot) return x;
	return -siz;
}

int64_t get_length(int x, int y) {
	int64_t w = d0[x] + d0[y] + T[1].dsum[x] + T[1].dsum[y] + T[2].dist(x, y);
	return w;
}

struct diameter_t {
	int x, y;
	int64_t len;
	diameter_t() : x(-1), y(-1), len(-1) {

	}
	diameter_t(int x, int y) : x(x), y(y), len(get_length(x, y)) {

	}
} f[N][2];

diameter_t operator+(const diameter_t &a, const diameter_t &b) {
	if (a.len == -1) return b;
	if (b.len == -1) return a;
	diameter_t ans = (a.len >= b.len ? a : b);
	auto update = [&](int x, int y) {
		if (x == -1 || y == -1) return;
		int64_t len = get_length(x, y);
		if (len > ans.len) {
			ans.x = x;
			ans.y = y;
			ans.len = len;
		}
	};
	update(a.x, b.x); update(a.x, b.y);
	update(a.y, b.x); update(a.y, b.y);
	return ans;
}

diameter_t operator*(const diameter_t &a, const diameter_t &b) {
	if (a.len == -1) return diameter_t();
	if (b.len == -1) return diameter_t();
	diameter_t ans = diameter_t();
	auto update = [&](int x, int y) {
		if (x == -1 || y == -1) return;
		int64_t len = get_length(x, y);
		if (len > ans.len) {
			ans.x = x;
			ans.y = y;
			ans.len = len;
		}
	};
	update(a.x, b.x); update(a.x, b.y);
	update(a.y, b.x); update(a.y, b.y);
	return ans;
}

std::vector<int> sub[N];
auto cmp(const tree_t &T) {
	return [&](int i, int j) -> bool { return T.dfn[i] < T.dfn[j]; };
};

struct virtual_tree_t {
	std::vector<int> vadj[N], vertex_set;
	bool buc[N];
	bool alive;
	void declare_vertices(std::vector<int> S) {
		assert(!alive);
		vertex_set = S;
		for (int x : S)
			buc[x] = true;
		alive = true;
	}
	void add_edge(int x, int y) {
		assert(buc[x] && buc[y]);
		vadj[x].push_back(y); 
	}
	void destroy() {
		assert(alive);
		for (int x : vertex_set)
			vadj[x].clear();
		vertex_set.clear();
		alive = false;
	}
} VT;

void work(int x) {
	f[x][0] = f[x][1] = diameter_t();
	if (col[x] != 0)
		f[x][col[x] - 1] = diameter_t(x, x);
	for (int y : VT.vadj[x]) {
		work(y);
		ans = std::max(ans, (f[x][0] * f[y][1]).len - 2 * T[1].dsum[x]);
		ans = std::max(ans, (f[x][1] * f[y][0]).len - 2 * T[1].dsum[x]);
		f[x][0] = f[x][0] + f[y][0];
		f[x][1] = f[x][1] + f[y][1];
	}
}

std::vector<int> build_virtual_tree(const tree_t &T, const std::vector<int> &vertices) {
	std::vector<int> all = vertices;
	std::sort(all.begin(), all.end(), cmp(T));
	int n_cur = all.size();
	for (int i = 0; i + 1 < n_cur; ++i)
		all.push_back(T.LCA(all[i], all[i + 1]));
	all.push_back(1);
	std::sort(all.begin(), all.end(), cmp(T));
	all.erase(std::unique(all.begin(), all.end()), all.end());
	std::stack<int> current_chain;
	VT.declare_vertices(all);
	for (int x : all) {
		while (!current_chain.empty() && !T.is_ancestor(current_chain.top(), x))
			current_chain.pop();
		if (!current_chain.empty())
			VT.add_edge(current_chain.top(), x);
		current_chain.push(x);
	}
	return all;
}

void solve(int x) {
	x = get_centroid(x, get_size(x));
	ban[x] = true;
	d0[x] = 0;
	auto travel = [&](auto &self, int x, int fa, int64_t d, auto &sub) -> void {
		sub.push_back(x);
		d0[x] = d;
		for (auto [y, w] : T[0].adj[x])
			if (y != fa && !ban[y]) {
				self(self, y, x, d + w, sub);
			}
	};
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
		std::greater<std::pair<int, int>>> subtrees;
	for (auto [y, w] : T[0].adj[x]) {
		if (!ban[y]) {
			sub[y].clear();
			travel(travel, y, x, w, sub[y]);
			subtrees.emplace(sub[y].size(), y);
		}
	}
	auto merge = [&](int x, int y) {
		std::vector<int> all;
		for (int &t : sub[x])
			all.push_back(t), col[t] = 1;
		for (int &t : sub[y])
			all.push_back(t), col[t] = 2;
		build_virtual_tree(T[1], all);
		work(1);
		for (int &t : all)
			col[t] = 0;
		sub[x] = all;
		sub[y].clear();
		VT.destroy();
	};
	sub[x] = {x};
	subtrees.emplace(sub[x].size(), x);
	while (subtrees.size() > 1) {
		auto [sizx, x] = subtrees.top(); subtrees.pop();
		auto [sizy, y] = subtrees.top(); subtrees.pop();
		merge(x, y);
		subtrees.emplace(sub[x].size(), x);
	}
	for (auto [y, w] : T[0].adj[x])
		if (!ban[y]) {
			solve(y);
		}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int n;
	std::cin >> n;
	for (int i = 0; i < 3; ++i) {
		for (int _ = 0; _ < n - 1; ++_) {
			int x, y; int64_t w;
			std::cin >> x >> y >> w;
			T[i].add_edge(x, y, w);
		}
		T[i].init();
	}
	solve(1);
	std::cout << ans << '\n';
}

詳細信息

Subtask #1:

score: 6
Accepted

Test #1:

score: 6
Accepted
time: 4ms
memory: 28344kb

input:

100
30 18 1
97 86 1
59 6 1
21 66 1
75 9 1
44 70 1
96 49 1
76 47 1
98 91 1
72 86 1
23 64 1
99 22 1
12 24 1
30 88 1
83 32 1
13 67 1
1 89 1
27 37 1
73 3 1
22 34 1
14 83 1
67 26 1
33 76 1
74 56 1
42 19 1
83 77 1
99 45 1
7 75 1
74 14 1
48 80 1
40 54 1
25 79 1
41 22 1
69 53 1
2 19 1
5 58 1
45 44 1
77 65 1...

output:

60

result:

ok 1 number(s): "60"

Test #2:

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

input:

100
36 18 764400639319
6 82 965370388469
98 56 328686845230
77 71 666659813016
48 8 612512140999
60 12 535238066104
50 64 183914993593
17 42 314347337129
73 94 750496153345
48 95 526027758993
48 33 343993724484
60 7 81676899941
29 42 867180722090
2 36 709041391542
26 7 875419023554
69 55 26162372073...

output:

28839383713177

result:

ok 1 number(s): "28839383713177"

Test #3:

score: 0
Accepted
time: 6ms
memory: 24320kb

input:

100
17 38 516345893761
61 43 800047425088
61 90 892027762023
28 63 82861509594
39 19 539023565558
17 31 516016284995
14 74 909210321126
1 59 446526063367
30 36 572284974967
76 29 559342888529
90 87 783022046397
77 74 212141810464
91 41 440702967454
37 90 447183549575
34 14 743250991349
33 73 1919562...

output:

29034145092818

result:

ok 1 number(s): "29034145092818"

Test #4:

score: 0
Accepted
time: 15ms
memory: 25344kb

input:

3000
2273 1274 1
1105 333 1
2812 1400 1
1675 2358 1
879 1124 1
81 172 1
737 194 1
2022 2814 1
1526 2531 1
1918 2806 1
2530 2328 1
1136 2805 1
1839 1659 1
1521 465 1
2784 1250 1
2216 896 1
2707 735 1
2576 384 1
1080 333 1
279 2099 1
1597 527 1
2889 1274 1
1274 830 1
1915 1960 1
1409 739 1
2079 1882 1...

output:

1374

result:

ok 1 number(s): "1374"

Test #5:

score: 0
Accepted
time: 29ms
memory: 27384kb

input:

3000
2452 2192 1
644 2612 1
2595 933 1
288 543 1
1264 1935 1
1079 1993 1
49 333 1
222 320 1
955 1696 1
1305 719 1
262 365 1
180 2195 1
2101 1079 1
241 1570 1
1333 2897 1
1778 1084 1
619 74 1
1136 2973 1
1609 729 1
760 2628 1
1496 2825 1
2656 2608 1
1072 2938 1
1992 1901 1
2117 2955 1
2163 655 1
1219...

output:

505

result:

ok 1 number(s): "505"

Test #6:

score: 0
Accepted
time: 27ms
memory: 25252kb

input:

3000
2452 2192 113682126551
644 2612 245124539322
2595 933 648579665589
288 543 644767834741
1264 1935 304991555894
1079 1993 465709110936
49 333 21149003221
222 320 957518812946
955 1696 367259582174
1305 719 622667985923
262 365 832697451706
180 2195 6256439354
2101 1079 308361891209
241 1570 7919...

output:

260227449564365

result:

ok 1 number(s): "260227449564365"

Test #7:

score: 0
Accepted
time: 23ms
memory: 25296kb

input:

3000
1285 1357 946993769110
945 2606 452708275229
1865 1783 318328933337
2916 2135 295276586794
24 2272 171835109769
880 2598 199999462549
2295 2133 289327444476
330 2541 101220064299
2907 2329 143218863002
931 1143 528558182366
982 2469 434338685566
709 2106 700125340433
767 597 623447351531
1283 5...

output:

961141735746406

result:

ok 1 number(s): "961141735746406"

Subtask #2:

score: 3
Accepted

Test #8:

score: 3
Accepted
time: 917ms
memory: 75960kb

input:

100000
34240 34239 272074692821
5033 5032 77913724980
24795 24794 526969139707
19234 19233 612978877731
74574 74575 939868775394
54407 54406 39298474908
50302 50303 7684922585
25748 25749 338691982142
53062 53063 311351193040
86507 86506 848724815374
41651 41652 967687200600
23178 23177 283455595065...

output:

149585023636574946

result:

ok 1 number(s): "149585023636574946"

Subtask #3:

score: 10
Accepted

Dependency #2:

100%
Accepted

Test #9:

score: 10
Accepted
time: 856ms
memory: 55820kb

input:

100000
68879 80762 650581276562
68879 70471 87319165587
34110 65508 226550471548
47813 96799 850591349682
96799 9363 730222889682
76718 56304 478710326407
44968 64822 599694053165
52203 29016 788591471552
609 28228 922793395662
24915 24231 312991810927
39645 68879 700550291353
72529 71210 6831319185...

output:

5607727879956726

result:

ok 1 number(s): "5607727879956726"

Test #10:

score: 0
Accepted
time: 1035ms
memory: 62548kb

input:

100000
96286 45970 871746966499
17459 8428 954271847777
53992 7268 184576974194
22988 90758 173267980761
99700 19389 885757588916
75985 37272 506155120831
58308 12423 878338631126
79832 76243 290198531648
43908 30423 448650219921
64313 80676 737428897151
24053 94457 306399943324
1991 49766 721248680...

output:

43499460165553425

result:

ok 1 number(s): "43499460165553425"

Test #11:

score: 0
Accepted
time: 1047ms
memory: 60188kb

input:

100000
50442 91326 807312750909
65431 90274 44358992506
38691 82681 532220709872
92684 33107 20046023007
16049 60224 110758605948
29985 67862 753287624483
3188 43620 369355816121
11790 1056 386153901166
16352 17394 344580775329
83236 43536 768517437228
38544 25238 820929668536
53289 94157 3116835987...

output:

33192863625633651

result:

ok 1 number(s): "33192863625633651"

Subtask #4:

score: 16
Accepted

Dependency #3:

100%
Accepted

Test #12:

score: 16
Accepted
time: 409ms
memory: 48788kb

input:

50000
15573 42113 1
48656 21453 1
8016 9473 1
42113 4453 1
48152 26000 1
26692 38361 1
41783 3973 1
5234 34388 1
28007 13961 1
13284 12780 1
47324 24416 1
13086 41121 1
2323 18079 1
26000 39969 1
3521 11922 1
47473 36094 1
321 25581 1
26000 26 1
25553 429 1
34657 22814 1
21714 42113 1
27943 34697 1
...

output:

108053

result:

ok 1 number(s): "108053"

Test #13:

score: 0
Accepted
time: 457ms
memory: 49184kb

input:

50000
37313 28352 297109201700
43122 3134 503423353179
30070 15978 768718647068
95 31947 226771628067
10384 2291 64430271374
21825 13867 785862850645
29483 31817 603314359964
40878 39721 816372197145
38381 18201 928889714354
5701 31161 813967183573
31179 730 518205119448
2749 14314 913319820089
4385...

output:

58182813691314995

result:

ok 1 number(s): "58182813691314995"

Test #14:

score: 0
Accepted
time: 893ms
memory: 71332kb

input:

100000
63569 18586 494948807237
63569 25616 690530217233
78522 77428 634125774509
6111 73630 575511184822
94875 44355 656124873001
68442 57048 480374907267
78903 15128 693031831293
1250 32520 258034304239
27736 78542 108599198867
21890 79175 317381343600
7023 114 15288477699
73630 72770 476548154246...

output:

103618969191653786

result:

ok 1 number(s): "103618969191653786"

Subtask #5:

score: 11
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #15:

score: 11
Accepted
time: 574ms
memory: 43432kb

input:

50000
14571 32750 1
20225 42031 1
1514 14424 1
14571 20686 1
47598 34180 1
13865 17028 1
4525 12292 1
39152 30136 1
18291 40835 1
36102 23931 1
5778 22066 1
21358 42812 1
34260 26099 1
47356 35763 1
8865 10586 1
3541 42812 1
3689 33483 1
18076 35759 1
46053 40835 1
2710 4764 1
6983 1205 1
36202 1880...

output:

32053

result:

ok 1 number(s): "32053"

Test #16:

score: 0
Accepted
time: 591ms
memory: 41016kb

input:

50000
13808 1684 501382717492
10620 31442 504760356651
30874 25285 499968540869
21692 27284 938064714570
38546 44776 719819740663
34715 39590 681914856813
42086 24358 128298106765
19304 14986 976801829520
31887 24931 907322524180
30668 46232 703664937817
42441 26010 842290930945
24273 2908 193438133...

output:

10032744408264853

result:

ok 1 number(s): "10032744408264853"

Test #17:

score: 0
Accepted
time: 1027ms
memory: 55688kb

input:

100000
38902 10718 357590796915
14130 38902 728735665479
22844 78151 799023285167
46143 38902 442273910381
20910 2443 446515674547
5507 59790 293844456906
39722 13500 333638689573
59790 31299 361015115724
26919 5233 662150191381
38902 7115 949809588496
25726 4326 37160007472
10424 38902 748836307195...

output:

17233532972163524

result:

ok 1 number(s): "17233532972163524"

Subtask #6:

score: 15
Accepted

Dependency #3:

100%
Accepted

Test #18:

score: 15
Accepted
time: 419ms
memory: 48484kb

input:

50000
23402 6819 1
42455 15413 1
23843 48041 1
18601 43275 1
28668 6449 1
27038 38317 1
906 43994 1
21899 21475 1
34987 2659 1
29454 46863 1
26984 45566 1
29263 36883 1
21430 43142 1
29810 15994 1
5255 40038 1
37486 47856 1
28321 21589 1
48178 18997 1
47028 41282 1
27130 10266 1
49989 11954 1
31495 ...

output:

105107

result:

ok 1 number(s): "105107"

Test #19:

score: 0
Accepted
time: 437ms
memory: 49764kb

input:

50000
2098 41758 780259816953
361 49984 911242565309
48535 88 576181910272
15557 9636 214298019802
44998 16036 792980353079
44418 4175 654827122401
9483 11240 258307336945
14889 14196 568739520376
4397 36802 35593510213
16176 2201 798032283327
27105 26568 952969271745
21939 11216 599428759198
12496 ...

output:

53017348038863624

result:

ok 1 number(s): "53017348038863624"

Test #20:

score: 0
Accepted
time: 1139ms
memory: 74468kb

input:

100000
28962 60894 1
41981 7712 1
48888 41583 1
67610 3925 1
50715 35404 1
54801 33999 1
40943 16560 1
51636 51406 1
74964 7655 1
43617 16142 1
49759 45481 1
25429 8353 1
22510 92502 1
18236 14193 1
20551 11034 1
19878 76135 1
70368 68688 1
82055 36205 1
89489 47882 1
72792 10341 1
23883 9960 1
5881...

output:

221677

result:

ok 1 number(s): "221677"

Test #21:

score: 0
Accepted
time: 1021ms
memory: 72488kb

input:

100000
22032 81945 711463523315
39590 56913 579925912966
420 86464 583634667909
45840 20924 250170738646
32336 2329 214952379308
11654 77492 343065862168
47726 54909 986009520743
8477 72616 614480907720
15149 7031 174174173974
29575 54865 770317464239
93693 75123 8843652534
38735 98892 209558516329
...

output:

110982475402008320

result:

ok 1 number(s): "110982475402008320"

Subtask #7:

score: 13
Accepted

Dependency #6:

100%
Accepted

Test #22:

score: 13
Accepted
time: 473ms
memory: 42932kb

input:

50000
42324 31858 1
25167 11460 1
35235 29251 1
26182 20840 1
28733 35885 1
41684 21435 1
20382 30570 1
40744 38522 1
31663 299 1
8772 47351 1
35273 14185 1
34058 41606 1
4362 10854 1
5629 17301 1
47639 38928 1
13005 32949 1
37439 5706 1
38383 5800 1
28016 44543 1
32395 12368 1
16689 32141 1
7860 99...

output:

71017

result:

ok 1 number(s): "71017"

Test #23:

score: 0
Accepted
time: 431ms
memory: 42212kb

input:

50000
46051 19054 637398872350
36787 13767 449752580175
6395 15784 670584382731
18570 14942 907194017385
11521 30539 697127397016
12414 13767 677880525680
43690 28422 924605317646
2849 15784 808930687066
15784 11244 720810891484
48607 15784 345865304980
12160 13767 235518235693
46612 109 88899667928...

output:

31971778230458647

result:

ok 1 number(s): "31971778230458647"

Test #24:

score: 0
Accepted
time: 1188ms
memory: 61972kb

input:

100000
28355 94047 1
39984 26263 1
78593 15252 1
64630 80166 1
57084 50600 1
70498 43467 1
68050 66630 1
79794 48615 1
48237 77222 1
49322 98180 1
41923 56940 1
91749 65803 1
55217 57652 1
55179 26704 1
57957 38984 1
95303 11800 1
41782 28950 1
90771 18997 1
25538 79762 1
19464 5837 1
14118 78152 1
...

output:

139797

result:

ok 1 number(s): "139797"

Test #25:

score: 0
Accepted
time: 1163ms
memory: 59988kb

input:

100000
99570 43214 938915807434
22486 5302 183548456649
75208 93230 47825695897
96201 93519 768059203530
65171 7379 965316098143
9481 47995 850503795505
12166 19383 743611422000
84595 66817 747920435321
14101 60549 307871288502
3389 99917 219014253787
79362 52201 980907771512
8981 93332 87066815173
...

output:

56144624446629915

result:

ok 1 number(s): "56144624446629915"

Subtask #8:

score: 26
Accepted

Test #26:

score: 26
Accepted
time: 662ms
memory: 42344kb

input:

50000
30967 24381 1
34287 29639 1
30009 26335 1
19251 18579 1
47627 32209 1
33524 26759 1
35659 36891 1
48851 23630 1
38099 49242 1
44427 38457 1
30681 47140 1
22194 30310 1
4570 45239 1
47245 4295 1
13316 2639 1
40278 35760 1
8162 37359 1
34287 23122 1
47483 3145 1
45990 4191 1
38373 25099 1
14256 ...

output:

23494

result:

ok 1 number(s): "23494"

Test #27:

score: 0
Accepted
time: 642ms
memory: 41080kb

input:

50000
36243 12994 221852616813
38665 31455 259467030152
3400 36243 704954898318
10281 30203 182252672400
38665 22906 850281381899
38665 21045 228859606075
29239 11249 878601554540
6793 22593 973567665178
39474 20459 737995169109
35291 2827 967329283087
27672 29833 825318536265
35329 1225 74244984838...

output:

10323683045861801

result:

ok 1 number(s): "10323683045861801"

Test #28:

score: 0
Accepted
time: 1742ms
memory: 57692kb

input:

100000
71058 41914 1
41087 95920 1
68564 26720 1
50317 18014 1
71722 44090 1
27639 98457 1
17511 44444 1
44392 69365 1
27757 32504 1
80282 11798 1
70658 56363 1
61257 91194 1
93224 98505 1
51035 26720 1
92988 7461 1
26321 2343 1
76905 15902 1
19231 53012 1
31597 36893 1
59424 78052 1
4517 70480 1
44...

output:

33447

result:

ok 1 number(s): "33447"

Test #29:

score: 0
Accepted
time: 1582ms
memory: 58164kb

input:

100000
10447 63188 479772426814
12410 40141 214732398034
82806 75172 595270682409
3555 44353 247750387918
72049 8019 814721288552
86610 15950 283782850807
10500 10036 203282026682
56457 73354 878841319503
2402 74064 545474630711
39412 58991 950030121696
2038 30103 668905478740
87325 74408 9666510034...

output:

17411504279678081

result:

ok 1 number(s): "17411504279678081"

Test #30:

score: 0
Accepted
time: 1616ms
memory: 56012kb

input:

100000
1357 38389 946176282148
52096 53148 918394577890
73016 39142 196454811082
90152 48238 806433127747
77631 25873 723794540834
39142 61437 805498849671
20414 62187 795204357846
39142 95224 435108363120
54881 21127 456324571386
54881 845 598265074658
25873 79134 948969203815
16333 11189 954971583...

output:

12465466385930189

result:

ok 1 number(s): "12465466385930189"

Test #31:

score: 0
Accepted
time: 1258ms
memory: 56504kb

input:

100000
68519 31809 974290851908
26015 64089 132490834667
14818 92426 474661521774
51536 4291 188764838448
42865 58448 85991518758
36370 88005 353998441415
99983 58951 234351893298
88684 88540 28635756450
69552 21877 173038013853
81875 8234 991723805714
32560 47084 74557781353
35685 65405 60652715241...

output:

14149163748841351

result:

ok 1 number(s): "14149163748841351"

Extra Test:

score: 0
Extra Test Passed