QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#884271#10066. Many Pairsguleng2007#100 ✓1032ms53808kbC++202.7kb2025-02-05 23:13:432025-02-05 23:13:44

Judging History

This is the latest submission verdict.

  • [2025-02-05 23:13:44]
  • Judged
  • Verdict: 100
  • Time: 1032ms
  • Memory: 53808kb
  • [2025-02-05 23:13:43]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+5;

vector <int> g[N];
int sz[N], fa[N], dep[N], son[N];

void dfs1(int x)
{
	sz[x]=1;
	for(auto to:g[x])
		if(to!=fa[x])
		{
			fa[to]=x;
			dep[to]=dep[x]+1;
			dfs1(to);
			sz[x] += sz[to];
			if(sz[to]>sz[son[x]])
				son[x]=to;
		}
}

int top[N], dfsn[N], point[N], Indx;

void dfs2(int x,int t)
{
	top[x]=t, dfsn[x]=++Indx, point[Indx]=x;
	if(son[x])
		dfs2(son[x],t);

	for(auto to:g[x])
		if(to!=fa[x] && to!=son[x])
			dfs2(to,to);
}

int lca(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);

		x=fa[top[x]];
	}

	if(dep[x]<dep[y])
		return x;
	return y;
}

struct node
{
	int x,y,c;
};

vector <node> vec[N];
int p[N], sum[N], ans[N], tot[N], out[N], add[N], alltot;
map <pair<int,int>,int> Edge;

int getfa(int x)
{
	if(x!=p[x])
		p[x]=getfa(p[x]);
	return p[x];
}

void merge(int x,int y)
{
	int fax=getfa(x), fay=getfa(y);
	p[fax]=fay;
}

void dfs3(int x)
{
	for(auto to:g[x])
		if(to!=fa[x])
		{
			dfs3(to);
			sum[x] += sum[to];
			tot[x] += tot[to];
		}

	Edge.clear();
	int totAdd=0;
	for(auto p:vec[x])
	{
		sum[x] += p.c;
		if(p.x==x || p.y==x)
			sum[getfa(p.x+p.y-x)] += p.c, add[getfa(p.x+p.y-x)] += p.c, totAdd += p.c;
		else
		{
			out[getfa(p.x)] += p.c;
			out[getfa(p.y)] += p.c;
			Edge[make_pair(min(getfa(p.x),getfa(p.y)),max(getfa(p.x),getfa(p.y)))] += p.c;
		}
	}

	vector <int> val;
	for(auto to:g[x])
		if(to!=fa[x])
			val.push_back(sum[to]);

	sort(val.begin(),val.end(),greater<int>());

	if(val.size()>=2)
		ans[x]=max(ans[x],val[0]+val[1]);
	else if(val.size())
		ans[x]=max(ans[x],val[0]);

	for(auto p:Edge)
		ans[x]=max(ans[x],sum[p.first.first]+sum[p.first.second]+p.second);

	vector<int> son;
	for(auto to:g[x])
		if(to!=fa[x])
			son.push_back(to);

	if(!son.size())
		ans[x]=alltot;
	else
	{
		for(auto to:son)
		{
			int val=alltot;
			for(auto oth:son)
				if(oth!=to)
					val -= tot[oth];
			val += sum[x]-sum[to]-out[to]-totAdd+add[to];
			ans[x]=max(ans[x],val);
		}
	}

	for(auto to:g[x])
		if(to!=fa[x])
			merge(to,x);
}

signed main()
{
	int n,k;
	cin >> n >> k;
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%lld %lld",&x,&y);
		g[x].push_back(y);
		g[y].push_back(x);
	}

	dep[1]=1;
	dfs1(1);
	dfs2(1,1);

	for(int i=1;i<=k;i++)
	{
		int a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		alltot += c;
		if(a==b)
			assert(0);

		tot[a] += c, tot[b] += c;
		vec[lca(a,b)].push_back((node){a,b,c});
	}

	for(int i=1;i<=n;i++)
		p[i]=i;

	dfs3(1);

	for(int i=1;i<=n;i++)
		printf("%lld ",ans[i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 1ms
memory: 16224kb

input:

50 50
1 20
13 1
39 1
12 1
16 1
4 1
9 1
1 17
33 1
1 28
1 46
31 1
1 23
44 1
15 1
1 7
14 1
1 40
1 25
1 34
11 1
6 1
1 30
1 3
42 1
1 48
35 1
27 1
1 45
29 1
10 1
19 1
2 1
38 1
41 1
1 37
1 32
18 1
47 1
26 1
22 1
1 5
1 50
49 1
1 21
43 1
1 8
1 36
24 1
26 20 640
41 45 742
39 15 520
20 18 703
47 16 391
2 19 97...

output:

1864 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 

result:

ok single line: '1864 35112 35112 35112 35112 3... 35112 35112 35112 35112 35112 '

Test #2:

score: 12
Accepted
time: 1ms
memory: 16220kb

input:

50 50
50 1
28 1
1 15
16 1
1 38
5 1
1 23
1 42
37 1
39 1
1 4
32 1
10 1
18 1
1 19
1 36
46 1
1 34
20 1
2 1
1 26
44 1
24 1
1 30
1 43
17 1
7 1
12 1
1 22
29 1
1 3
31 1
33 1
1 14
1 49
48 1
13 1
1 45
25 1
35 1
1 41
1 21
8 1
27 1
9 1
1 40
1 6
47 1
1 11
14 19 680
44 37 476
39 12 463
16 7 354
49 41 430
38 42 77...

output:

1250 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 

result:

ok single line: '1250 32887 32887 32887 32887 3... 32887 32887 32887 32887 32887 '

Test #3:

score: 12
Accepted
time: 1ms
memory: 14180kb

input:

50 50
1 31
17 1
33 1
13 1
32 30
34 1
43 36
1 14
10 1
1 8
44 4
7 1
21 48
1 22
1 23
15 1
37 1
1 24
1 42
1 9
47 1
1 4
48 1
1 41
32 1
3 4
27 1
11 4
32 50
46 4
1 28
18 1
49 1
6 4
17 29
4 40
25 1
16 48
1 45
1 36
12 4
4 2
32 20
19 38
32 39
1 5
1 19
1 35
26 1
13 15 637
22 40 788
42 39 443
48 19 415
14 39 45...

output:

3540 31749 31749 23997 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31385 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31445 31749 31749 

result:

ok single line: '3540 31749 31749 23997 31749 3... 31749 31749 31445 31749 31749 '

Test #4:

score: 12
Accepted
time: 1ms
memory: 14188kb

input:

50 50
37 31
17 9
33 21
13 36
10 30
34 39
43 28
11 14
10 42
23 8
44 41
7 19
21 24
30 22
17 23
15 24
37 20
38 24
37 42
26 9
47 11
1 4
48 32
7 41
32 4
3 39
27 38
11 21
37 50
46 14
6 28
18 44
49 8
6 11
47 29
5 40
25 30
16 39
6 45
48 36
12 2
28 2
23 20
34 38
5 39
30 5
13 19
18 35
26 18
13 15 637
22 40 78...

output:

31749 31749 31749 31749 28545 29418 31749 31749 31749 31749 29434 31749 31749 31749 31749 31749 31749 30513 31749 31749 31041 31749 26850 29829 31749 31749 31749 30766 31749 29541 31749 31749 31749 31749 31749 31749 31189 30356 30338 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 31749 

result:

ok single line: '31749 31749 31749 31749 28545 ... 31749 31749 31749 31749 31749 '

Test #5:

score: 12
Accepted
time: 0ms
memory: 18276kb

input:

50 50
50 26
28 38
21 15
16 1
36 38
5 45
19 23
10 42
37 6
39 27
20 4
32 48
10 28
18 23
29 19
18 36
46 11
8 34
20 46
2 39
47 26
44 16
24 9
31 30
35 43
17 44
7 5
12 4
12 22
29 22
25 3
31 9
33 34
43 14
15 49
48 33
13 42
13 45
25 7
35 3
14 41
2 21
8 40
27 30
9 50
17 40
41 6
47 37
32 11
14 19 680
44 37 47...

output:

32887 32887 32887 32887 32887 32887 32887 32887 32483 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 32887 

result:

ok single line: '32887 32887 32887 32887 32887 ... 32887 32887 32887 32887 32887 '

Test #6:

score: 12
Accepted
time: 1ms
memory: 14188kb

input:

50 50
15 20
13 17
39 43
12 50
16 27
4 45
9 42
34 17
33 44
24 28
32 46
31 5
38 23
44 26
15 35
40 7
14 13
6 40
30 25
37 34
11 29
6 49
7 30
2 3
42 10
47 48
35 8
27 22
20 45
29 25
10 3
19 23
2 19
38 31
41 14
4 37
18 32
18 48
47 11
26 9
22 12
46 5
36 50
49 1
16 21
43 41
28 8
33 36
24 21
26 20 640
41 45 7...

output:

35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 35112 

result:

ok single line: '35112 35112 35112 35112 35112 ... 35112 35112 35112 35112 35112 '

Test #7:

score: 12
Accepted
time: 0ms
memory: 14000kb

input:

50 50
8 1
34 3
1 34
41 11
32 20
13 32
44 1
9 1
2 46
43 1
34 36
38 43
8 47
29 43
18 34
2 12
41 14
43 35
39 23
10 42
30 9
42 28
33 2
8 4
39 25
7 22
1 22
22 27
2 1
45 39
40 22
48 42
2 37
26 39
1 42
22 24
42 5
43 31
39 1
1 41
17 39
16 9
49 34
21 9
22 50
32 1
8 19
15 32
41 6
31 47 905
35 20 568
10 19 956...

output:

3187 27989 30442 30442 30442 30442 30442 28534 27565 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 30442 28692 30442 30442 30442 30442 30442 30442 30442 30442 30442 28374 30442 29539 30442 30442 30442 30442 25323 30442 30004 28854 25759 30442 30442 30442 30442 30442 30442 30442 

result:

ok single line: '3187 27989 30442 30442 30442 3... 30442 30442 30442 30442 30442 '

Test #8:

score: 12
Accepted
time: 0ms
memory: 13896kb

input:

50 50
50 9
38 4
3 40
14 1
7 21
27 10
29 44
47 9
25 32
15 49
12 44
23 30
11 50
25 28
35 45
36 46
32 29
37 2
12 20
5 41
45 30
37 14
17 8
28 6
3 11
1 4
24 39
21 16
35 10
34 24
48 16
41 15
40 23
43 34
43 22
31 20
7 42
19 1
39 31
36 8
19 6
46 18
48 18
5 22
38 13
17 33
26 42
2 26
13 47
3 21 797
30 28 341
...

output:

20937 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 33754 

result:

ok single line: '20937 33754 33754 33754 33754 ... 33754 33754 33754 33754 33754 '

Subtask #2:

score: 13
Accepted

Test #9:

score: 13
Accepted
time: 12ms
memory: 14804kb

input:

5000 500
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 4554...

output:

7043 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 3...

result:

ok single line: '7043 332097 332097 332097 3320...97 332097 332097 332097 332097 '

Test #10:

score: 13
Accepted
time: 3ms
memory: 18508kb

input:

5000 500
2967 950
1 4700
3353 2511
4023 1
1300 4532
2356 3798
1300 3894
997 4696
999 3080
35 4766
3785 2028
793 2309
63 741
1766 3785
3285 586
3353 867
3730 1
2980 3727
1065 997
2678 2375
2751 1683
4691 1400
2827 2706
1548 4078
1 1376
1443 3224
2629 4159
1552 3353
4536 1300
3103 3632
3368 865
2174 1...

output:

9048 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 318566 319126 3...

result:

ok single line: '9048 319126 319126 319126 3191...26 319126 319126 319126 319126 '

Test #11:

score: 13
Accepted
time: 3ms
memory: 12668kb

input:

5000 500
2967 3037
3043 4700
174 2511
4023 2384
1654 4532
2356 1104
386 3894
2067 4696
999 4577
35 2198
1623 2028
793 3636
63 3998
1766 2649
3285 3906
608 867
3730 247
3566 3727
1065 2247
728 2375
2649 1683
4691 4296
2827 4197
1548 2888
2904 1376
3566 3224
2629 3234
1552 3243
4536 4202
201 3632
2417...

output:

319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 318136 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126 319126...

result:

ok single line: '319126 319126 319126 319126 31...75 319126 319126 319126 319126 '

Test #12:

score: 13
Accepted
time: 1ms
memory: 15620kb

input:

5000 500
4054 2035
2103 899
2889 2612
3899 2285
1062 1572
2838 4500
1507 3608
2582 1752
2127 2880
201 2937
3989 1262
1645 1300
4071 1650
2576 3875
333 3547
1378 1145
3878 36
1152 3240
1812 2047
188 4983
3564 3050
4965 756
1044 1305
3217 1162
3789 4820
2377 833
1640 4944
1363 263
1913 4731
2712 4040
...

output:

332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 332097 331221 332097 332097 332097...

result:

ok single line: '332097 332097 332097 332097 33...97 332097 332097 332097 332097 '

Test #13:

score: 13
Accepted
time: 1ms
memory: 14676kb

input:

5000 500
1507 2684
3377 3492
1 3146
2137 1967
2279 1502
1396 208
4036 4412
527 3215
2546 2615
308 598
4477 1919
4278 1250
665 3225
3124 1358
1574 1322
1092 3836
2763 1117
4183 1
208 1734
2342 2012
3058 2174
3120 376
1601 2597
2298 422
69 2437
3089 598
1117 1835
3862 1636
63 2693
2615 1195
4488 3247
...

output:

2524 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 328379 3...

result:

ok single line: '2524 328379 328379 328379 3283...79 328379 328379 328379 328379 '

Test #14:

score: 13
Accepted
time: 3ms
memory: 18572kb

input:

5000 500
3349 365
1199 1403
2251 3476
2517 1051
2681 3714
563 1
4526 1229
278 4460
3927 130
2542 998
2792 1306
385 4946
827 2766
3048 936
4445 1364
4164 1173
2905 4252
2211 3387
1224 733
1629 4797
1372 1208
2134 322
4269 784
1340 2808
90 4603
1313 3956
3809 3295
912 3111
2377 3500
4015 1443
674 670
...

output:

3488 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 326958 3...

result:

ok single line: '3488 326958 326958 326958 3269...58 326958 326958 326958 326958 '

Subtask #3:

score: 17
Accepted

Test #15:

score: 17
Accepted
time: 11ms
memory: 17008kb

input:

5000 2000
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 455...

output:

2212740 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 13...

result:

ok single line: '2212740 130540162 130540162 13... 130540162 130540162 130540162 '

Test #16:

score: 17
Accepted
time: 2ms
memory: 12880kb

input:

5000 2000
2967 950
1 4700
3353 2511
4023 1
1300 4532
2356 3798
1300 3894
997 4696
999 3080
35 4766
3785 2028
793 2309
63 741
1766 3785
3285 586
3353 867
3730 1
2980 3727
1065 997
2678 2375
2751 1683
4691 1400
2827 2706
1548 4078
1 1376
1443 3224
2629 4159
1552 3353
4536 1300
3103 3632
3368 865
2174 ...

output:

3167789 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 12...

result:

ok single line: '3167789 129909272 129909272 12... 129909272 129909272 129909272 '

Test #17:

score: 17
Accepted
time: 1ms
memory: 14984kb

input:

5000 2000
2967 3037
3043 4700
174 2511
4023 2384
1654 4532
2356 1104
386 3894
2067 4696
999 4577
35 2198
1623 2028
793 3636
63 3998
1766 2649
3285 3906
608 867
3730 247
3566 3727
1065 2247
728 2375
2649 1683
4691 4296
2827 4197
1548 2888
2904 1376
3566 3224
2629 3234
1552 3243
4536 4202
201 3632
241...

output:

129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129741991 129909272 129909272 129803447 129909272 129833295 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 129909272 ...

result:

ok single line: '129909272 129909272 129909272 ... 129909272 129909272 129909272 '

Test #18:

score: 17
Accepted
time: 3ms
memory: 15708kb

input:

5000 2000
4054 2035
2103 899
2889 2612
3899 2285
1062 1572
2838 4500
1507 3608
2582 1752
2127 2880
201 2937
3989 1262
1645 1300
4071 1650
2576 3875
333 3547
1378 1145
3878 36
1152 3240
1812 2047
188 4983
3564 3050
4965 756
1044 1305
3217 1162
3789 4820
2377 833
1640 4944
1363 263
1913 4731
2712 4040...

output:

130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130504520 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130540162 130449373 130540162 130540162 ...

result:

ok single line: '130540162 130540162 130540162 ... 130540162 130540162 130540162 '

Test #19:

score: 17
Accepted
time: 1ms
memory: 14892kb

input:

5000 2000
1507 2684
3377 3492
1 3146
2137 1967
2279 1502
1396 208
4036 4412
527 3215
2546 2615
308 598
4477 1919
4278 1250
665 3225
3124 1358
1574 1322
1092 3836
2763 1117
4183 1
208 1734
2342 2012
3058 2174
3120 376
1601 2597
2298 422
69 2437
3089 598
1117 1835
3862 1636
63 2693
2615 1195
4488 3247...

output:

585252 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131912535 131...

result:

ok single line: '585252 131912535 131912535 131... 131912535 131912535 131912535 '

Test #20:

score: 17
Accepted
time: 2ms
memory: 18816kb

input:

5000 2000
3349 365
1199 1403
2251 3476
2517 1051
2681 3714
563 1
4526 1229
278 4460
3927 130
2542 998
2792 1306
385 4946
827 2766
3048 936
4445 1364
4164 1173
2905 4252
2211 3387
1224 733
1629 4797
1372 1208
2134 322
4269 784
1340 2808
90 4603
1313 3956
3809 3295
912 3111
2377 3500
4015 1443
674 670...

output:

664106 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130625863 130...

result:

ok single line: '664106 130625863 130625863 130... 130625863 130625863 130625863 '

Subtask #4:

score: 21
Accepted

Test #21:

score: 21
Accepted
time: 11ms
memory: 14928kb

input:

5000 5000
1 2035
2103 1
2889 1
3899 1
1 1572
2838 1
1 3608
2582 1
1 2880
201 1
3989 1
1 1300
4071 1
2576 4504
1 3547
1 1145
3878 1
1 3240
1 2047
1 4983
3564 1
4965 4504
1 1305
3217 1
1 4820
2377 1
1640 1
1363 1
1 4731
1 4040
1 3707
3364 1
1 79
1 4968
2679 1
1 3276
1 4709
1 4438
1 3420
1 828
4504 455...

output:

46132009 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 26490...

result:

ok single line: '46132009 2649064843 2649064843...49064843 2649064843 2649064843 '

Test #22:

score: 21
Accepted
time: 4ms
memory: 18992kb

input:

5000 5000
2967 950
1 4700
3353 2511
4023 1
1300 4532
2356 3798
1300 3894
997 4696
999 3080
35 4766
3785 2028
793 2309
63 741
1766 3785
3285 586
3353 867
3730 1
2980 3727
1065 997
2678 2375
2751 1683
4691 1400
2827 2706
1548 4078
1 1376
1443 3224
2629 4159
1552 3353
4536 1300
3103 3632
3368 865
2174 ...

output:

71850241 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 26492...

result:

ok single line: '71850241 2649293842 2649293842...49293842 2649293842 2649293842 '

Test #23:

score: 21
Accepted
time: 5ms
memory: 19092kb

input:

5000 5000
2967 3037
3043 4700
174 2511
4023 2384
1654 4532
2356 1104
386 3894
2067 4696
999 4577
35 2198
1623 2028
793 3636
63 3998
1766 2649
3285 3906
608 867
3730 247
3566 3727
1065 2247
728 2375
2649 1683
4691 4296
2827 4197
1548 2888
2904 1376
3566 3224
2629 3234
1552 3243
4536 4202
201 3632
241...

output:

2649293842 2649293842 2649293842 2649293842 2646227721 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2645738482 2649293842 2649293842 2645969915 2649293842 2648356916 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 2649293842 264...

result:

ok single line: '2649293842 2649293842 26492938...49293842 2649293842 2649293842 '

Test #24:

score: 21
Accepted
time: 1ms
memory: 19636kb

input:

5000 5000
4054 2035
2103 899
2889 2612
3899 2285
1062 1572
2838 4500
1507 3608
2582 1752
2127 2880
201 2937
3989 1262
1645 1300
4071 1650
2576 3875
333 3547
1378 1145
3878 36
1152 3240
1812 2047
188 4983
3564 3050
4965 756
1044 1305
3217 1162
3789 4820
2377 833
1640 4944
1363 263
1913 4731
2712 4040...

output:

2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2648921221 2649064843 2649064843 2648209327 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 2649064843 264...

result:

ok single line: '2649064843 2649064843 26490648...49064843 2648638772 2649064843 '

Test #25:

score: 21
Accepted
time: 3ms
memory: 14896kb

input:

5000 5000
1507 2684
3377 3492
1 3146
2137 1967
2279 1502
1396 208
4036 4412
527 3215
2546 2615
308 598
4477 1919
4278 1250
665 3225
3124 1358
1574 1322
1092 3836
2763 1117
4183 1
208 1734
2342 2012
3058 2174
3120 376
1601 2597
2298 422
69 2437
3089 598
1117 1835
3862 1636
63 2693
2615 1195
4488 3247...

output:

7623187 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 2618247942 261824...

result:

ok single line: '7623187 2618247942 2618247942 ...18247942 2618247942 2618247942 '

Test #26:

score: 21
Accepted
time: 4ms
memory: 17020kb

input:

5000 5000
3349 365
1199 1403
2251 3476
2517 1051
2681 3714
563 1
4526 1229
278 4460
3927 130
2542 998
2792 1306
385 4946
827 2766
3048 936
4445 1364
4164 1173
2905 4252
2211 3387
1224 733
1629 4797
1372 1208
2134 322
4269 784
1340 2808
90 4603
1313 3956
3809 3295
912 3111
2377 3500
4015 1443
674 670...

output:

11297999 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 2642116713 26421...

result:

ok single line: '11297999 2642116713 2642116713...42116713 2642116713 2642116713 '

Subtask #5:

score: 37
Accepted

Test #27:

score: 37
Accepted
time: 1032ms
memory: 43700kb

input:

200000 200000
1861 126068
196536 190176
143836 3918
183352 173153
149804 74098
192775 110127
106287 1861
103451 149418
160851 35753
171988 21209
156996 161848
138469 165694
35753 140239
100453 199546
110790 120346
73215 149224
19332 138469
72674 21209
127832 142648
86197 174308
181332 15643
148621 1...

output:

1640901879 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105069892770 105...

result:

ok single line: '1640901879 105069892770 105069...2770 105069892770 105069892770 '

Test #28:

score: 37
Accepted
time: 496ms
memory: 44672kb

input:

200000 200000
2382 192403
197579 147684
194742 148325
1 56247
1 175826
20450 169843
56282 157962
35439 23148
167857 188718
39400 148325
113907 141255
46371 171533
167857 72544
22484 2862
168483 179717
129650 84687
125504 68013
157962 141158
38125 97780
142578 107221
144112 197794
18220 141625
178525...

output:

452919450 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 1049...

result:

ok single line: '452919450 104912193174 1049121...3174 104912193174 104912193174 '

Test #29:

score: 37
Accepted
time: 201ms
memory: 45240kb

input:

200000 200000
193370 156594
178879 169822
188485 49555
142167 113607
88543 91370
40082 24702
170176 143197
86037 136335
124788 149914
127229 87267
56608 83528
54838 83090
135859 139657
71089 107918
132095 199626
65995 188324
164045 77933
65075 12184
192474 126503
8110 101059
124667 84142
144586 1042...

output:

5521214211 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105...

result:

ok single line: '5521214211 105092868359 105092...8359 105092868359 105092868359 '

Test #30:

score: 37
Accepted
time: 206ms
memory: 46172kb

input:

200000 200000
124940 156594
150898 169822
16843 49555
38352 113607
177800 91370
190376 24702
170176 181656
86037 153338
124788 82735
127229 136824
148943 83528
165182 83090
94542 139657
37761 107918
132095 150016
65995 170354
164045 69243
65075 167584
81106 126503
111084 101059
124667 46920
144586 1...

output:

105092868359 105092868359 105092868359 105092868359 105092868359 105092868359 105090261188 105092868359 105092868359 105092868359 105086313349 105092868359 105092868359 105092868359 105080234487 105091936202 105092868359 105090881282 105092868359 105092868359 105092868359 105092868359 105092868359 1...

result:

ok single line: '105092868359 105092868359 1050...8359 105092868359 105092868359 '

Test #31:

score: 37
Accepted
time: 203ms
memory: 48656kb

input:

200000 200000
2382 67359
184783 147684
194742 6889
154544 56247
33501 175826
20450 139236
56282 59860
168083 23148
70858 188718
39400 77559
34418 141255
46371 103684
9681 72544
22484 52567
168483 79774
129650 46603
125504 91822
90232 141158
146652 97780
111099 107221
144112 57276
81652 141625
16641 ...

output:

104912193174 104912193174 104912193174 104910164152 104912193174 104912193174 104912193174 104912193174 104910113995 104912193174 104912193174 104912193174 104909695449 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104912193174 104904950889 104912193174 104908934864 1...

result:

ok single line: '104912193174 104912193174 1049...4372 104912193174 104912193174 '

Test #32:

score: 37
Accepted
time: 217ms
memory: 51492kb

input:

200000 200000
102963 126068
196536 126498
143836 13714
133782 173153
49821 74098
61191 110127
106287 150498
103451 135215
160851 61335
171988 21851
156996 20834
178540 165694
76997 140239
49998 199546
110790 84229
73215 175160
19332 82354
72674 142705
127832 168459
168180 174308
181332 9967
148621 1...

output:

105069892770 105069892770 105069892770 105069626146 105069892770 105069050043 105069892770 105069892770 105069892770 105069892770 105061787453 105069892770 105069892770 105069892770 105063663105 105069892770 105061244203 105064688734 105069892770 105069892770 105069892770 105058259891 105069892770 1...

result:

ok single line: '105069892770 105069892770 1050...2770 105069892770 105069892770 '

Test #33:

score: 37
Accepted
time: 241ms
memory: 53808kb

input:

200000 200000
2984 112164
89186 30161
99278 45225
123287 10545
69545 96049
181936 139180
139087 137570
47847 1962
198021 39840
12981 127344
129981 190375
9908 198300
94711 57785
181076 1
101357 21405
16248 3533
8653 147103
29771 138893
13030 126155
1 186376
44455 97077
166321 92896
44593 79318
10132...

output:

3833363 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049835405 105049...

result:

ok single line: '3833363 105049835405 105049835...5405 105049835405 105049835405 '

Test #34:

score: 37
Accepted
time: 204ms
memory: 45192kb

input:

200000 200000
125785 175021
121216 174698
56177 99097
15000 103049
40120 26631
18900 1479
162976 56979
150160 101651
72559 33974
16349 165896
107535 50523
49769 150648
138388 186993
181343 152547
107356 117384
195758 4020
146299 14233
15901 30387
16643 79410
91097 146119
126668 191702
183335 53737
3...

output:

50750552 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 105133456481 10513...

result:

ok single line: '50750552 105133456481 10513345...6481 105133456481 105133456481 '

Extra Test:

score: 0
Extra Test Passed