QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276355#72. MergersDaiRuiChen007100 ✓562ms119336kbC++201.2kb2023-12-05 20:17:222023-12-05 20:17:23

Judging History

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

  • [2023-12-05 20:17:23]
  • 评测
  • 测评结果：100
  • 用时：562ms
  • 内存：119336kb
查看
  • [2023-12-05 20:17:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
vector <int> G[MAXN],C[MAXN];
int col[MAXN],fa[MAXN][20],dep[MAXN],cnt[MAXN],deg[MAXN];
inline void dfs0(int u,int fz) {
	fa[u][0]=fz,dep[u]=dep[fz]+1;
	for(int k=1;k<20;++k) fa[u][k]=fa[fa[u][k-1]][k-1];
	for(int v:G[u]) if(v^fz) dfs0(v,u);
}
inline void dfs1(int u,int fz) {
	for(int v:G[u]) if(v^fz) dfs1(v,u),cnt[u]+=cnt[v];
}
inline void dfs2(int u,int fz,int c) {
	for(int v:G[u]) if(v^fz) {
		if(!cnt[v]) ++deg[c],++deg[v],dfs2(v,u,v);
		else dfs2(v,u,c);
	}
}
inline int LCA(int u,int v) {
	if(dep[u]<dep[v]) swap(u,v);
	for(int k=19;~k;--k) if(dep[fa[u][k]]>=dep[v]) u=fa[u][k];
	if(u==v) return u;
	for(int k=19;~k;--k) if(fa[u][k]^fa[v][k]) u=fa[u][k],v=fa[v][k];
	return fa[u][0];
}
signed main() {
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	for(int i=1;i<=n;++i) scanf("%d",&col[i]),C[col[i]].push_back(i);
	dfs0(1,0);
	for(int i=1;i<=k;++i) {
		for(int j=1;j<(int)C[i].size();++j) {
			++cnt[C[i][0]],++cnt[C[i][j]],cnt[LCA(C[i][0],C[i][j])]-=2; 
		}
	}
	dfs1(1,0),dfs2(1,0,1);
	int ans=0;
	for(int i=1;i<=n;++i) if(!cnt[i]&&deg[i]==1) ++ans;
	printf("%d\n",(ans+1)/2);
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 3ms
memory: 32284kb

input:

1 1
1

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 4ms
memory: 34144kb

input:

3 2
2 1
3 1
2
2
1

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 3ms
memory: 32976kb

input:

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

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 3ms
memory: 31556kb

input:

7 7
5 7
4 7
6 4
1 3
2 6
3 4
6
7
2
4
5
3
1

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 3ms
memory: 33904kb

input:

10 5
1 3
9 6
8 6
3 10
3 2
1 6
8 7
2 5
9 4
1
1
3
2
2
5
3
1
4
2

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 4ms
memory: 33964kb

input:

100 1
7 97
63 10
65 17
26 85
50 92
92 20
28 83
92 51
5 4
56 2
18 27
16 73
24 78
73 10
35 6
49 10
20 11
42 23
30 7
24 69
38 87
53 45
25 3
93 57
64 47
84 73
20 91
97 31
99 45
20 38
76 9
98 94
40 72
77 38
37 7
88 8
37 78
73 8
90 61
45 68
32 29
55 37
46 88
17 14
46 12
83 100
35 40
71 20
32 92
57 88
92 6...

output:

0

result:

ok single line: '0'

Test #7:

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

input:

100 7
53 48
26 44
28 93
71 74
7 58
76 79
8 89
44 71
80 6
31 67
76 33
90 24
55 1
62 41
95 35
44 68
29 24
18 56
60 85
71 42
71 1
50 78
12 46
67 50
86 50
71 18
17 51
49 13
63 41
2 25
19 93
74 43
74 39
51 43
2 3
61 49
40 61
48 84
99 62
98 43
80 92
58 76
22 43
58 10
50 14
5 26
75 55
19 51
45 38
3 8
23 52...

output:

0

result:

ok single line: '0'

Test #8:

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

input:

9 6
7 6
9 1
2 4
4 5
9 2
8 6
9 3
8 1
3
1
6
4
4
2
5
5
6

output:

1

result:

ok single line: '1'

Test #9:

score: 0
Accepted
time: 4ms
memory: 33196kb

input:

100 6
45 58
90 65
28 24
76 32
97 92
50 81
38 17
98 40
81 21
68 56
36 78
45 12
74 31
72 30
20 35
61 85
39 8
69 40
54 60
80 25
5 95
95 27
54 70
19 21
20 12
85 93
16 88
95 48
46 14
45 72
40 7
37 14
72 47
22 10
45 31
75 69
32 6
73 22
56 99
11 35
43 55
1 56
15 56
35 42
100 55
49 34
76 33
87 45
78 70
90 8...

output:

1

result:

ok single line: '1'

Test #10:

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

input:

99 6
44 2
26 24
42 67
94 92
77 97
79 58
50 75
2 12
52 39
30 60
97 94
32 62
12 3
68 8
48 85
18 40
94 37
42 10
7 37
24 12
40 84
41 71
87 49
37 51
22 55
10 9
16 14
52 85
20 86
41 65
69 10
12 55
79 80
50 80
37 16
94 63
93 2
95 31
46 53
65 83
47 9
84 92
4 23
11 98
24 28
54 66
12 72
58 49
40 64
73 39
30 4...

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 4ms
memory: 34856kb

input:

84 7
10 47
56 65
25 60
13 7
22 55
67 23
30 64
37 12
14 6
55 7
68 66
11 70
65 23
58 56
82 74
3 61
9 29
68 38
80 8
80 5
78 75
75 69
75 31
26 77
18 3
52 49
45 38
6 67
80 26
5 46
39 26
68 40
12 30
14 25
84 21
48 69
43 63
38 36
1 39
12 10
25 31
53 15
74 6
59 30
47 4
32 24
82 33
20 31
44 40
54 38
51 28
32...

output:

2

result:

ok single line: '2'

Test #12:

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

input:

7 7
3 4
7 1
2 1
7 5
5 6
4 6
3
7
2
1
5
4
6

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 4ms
memory: 34016kb

input:

8 7
6 3
8 1
7 8
1 5
6 7
2 4
3 2
5
4
4
1
3
6
7
2

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 3ms
memory: 33456kb

input:

100 7
76 43
72 84
5 41
9 38
93 79
11 12
88 52
97 59
69 73
48 49
61 44
17 82
53 55
30 33
87 64
80 37
58 99
53 42
22 36
31 62
88 35
95 75
68 67
29 41
18 84
34 5
1 58
26 14
80 6
1 24
6 36
44 77
55 38
99 9
56 47
45 47
31 13
46 71
61 20
81 3
75 97
39 3
50 60
74 17
66 34
57 95
7 11
8 23
98 28
21 10
22 64
...

output:

0

result:

ok single line: '0'

Test #15:

score: 0
Accepted
time: 3ms
memory: 35084kb

input:

10 6
1 5
5 4
6 10
2 8
3 7
4 2
9 8
9 3
10 4
6
2
2
6
1
1
5
3
2
4

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 8ms
memory: 33960kb

input:

99 6
67 79
71 88
94 20
63 45
56 61
38 83
59 50
21 88
9 51
93 15
54 87
51 36
29 18
24 96
10 25
16 47
5 92
56 45
30 15
22 25
34 1
37 18
38 19
43 76
78 17
61 72
22 64
32 44
52 54
84 3
53 98
42 60
7 89
9 6
92 43
32 66
12 87
4 16
77 10
47 97
33 58
17 35
75 41
23 41
65 26
11 80
7 74
12 79
72 33
97 31
20 5...

output:

1

result:

ok single line: '1'

Test #17:

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

input:

100 6
14 86
25 42
67 97
24 34
12 18
97 31
93 69
1 56
71 100
82 43
55 69
12 33
79 39
88 73
60 62
28 35
21 11
41 89
17 29
63 61
59 75
54 96
13 89
47 58
43 45
50 56
91 74
11 7
20 40
71 94
73 6
38 64
35 23
22 5
93 38
90 54
10 57
23 36
3 22
99 72
74 66
27 18
55 30
9 92
50 78
85 87
26 68
28 60
8 46
44 14
...

output:

1

result:

ok single line: '1'

Test #18:

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

input:

84 7
17 69
82 35
23 65
17 61
57 68
19 40
54 77
10 9
26 11
25 81
19 39
41 71
20 57
28 60
31 83
3 30
31 64
22 52
37 29
38 7
58 59
42 66
66 46
20 25
11 43
71 48
56 51
44 53
76 62
67 21
1 22
46 8
49 33
72 47
38 33
7 70
18 36
43 59
15 9
32 69
30 12
5 4
15 14
8 21
55 39
50 48
41 16
45 4
63 38
24 11
36 12
...

output:

2

result:

ok single line: '2'

Test #19:

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

input:

7 7
7 3
6 3
1 3
4 3
5 3
3 2
7
4
5
6
2
3
1

output:

3

result:

ok single line: '3'

Test #20:

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

input:

15 7
7 9
4 7
7 2
14 7
7 6
7 12
7 3
11 7
7 15
5 7
7 13
8 7
10 7
7 1
7
6
3
4
4
1
3
7
6
3
5
7
2
2
1

output:

1

result:

ok single line: '1'

Test #21:

score: 0
Accepted
time: 7ms
memory: 33160kb

input:

100 7
56 87
56 74
39 56
83 56
99 56
28 56
56 3
56 62
48 56
56 20
24 56
56 17
30 56
11 56
56 40
73 56
56 61
56 6
56 16
2 56
56 94
19 56
56 85
56 70
56 68
57 56
56 75
53 56
56 1
56 59
71 56
47 56
55 56
56 31
80 56
93 56
56 66
14 56
56 76
56 97
56 89
35 56
56 49
12 56
56 82
58 56
100 56
95 56
9 56
56 4...

output:

0

result:

ok single line: '0'

Test #22:

score: 0
Accepted
time: 3ms
memory: 34916kb

input:

8 7
6 8
8 7
4 1
8 2
8 3
8 5
4 8
1
6
5
2
7
4
1
3

output:

2

result:

ok single line: '2'

Test #23:

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

input:

10 7
1 5
10 9
7 9
2 10
3 2
9 8
6 8
4 10
5 8
6
1
7
2
5
4
6
2
3
1

output:

1

result:

ok single line: '1'

Test #24:

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

input:

100 7
92 59
94 51
14 84
73 15
38 90
62 7
19 29
71 87
17 80
64 28
16 35
42 20
80 13
38 9
89 50
92 72
97 50
18 38
17 98
95 58
14 23
57 94
68 28
55 76
95 45
1 15
3 41
36 58
34 64
28 49
34 53
66 41
49 57
21 69
62 76
48 60
43 80
99 16
50 41
78 22
20 77
56 57
49 47
9 51
26 97
64 79
69 42
76 97
33 75
45 34...

output:

0

result:

ok single line: '0'

Subtask #2:

score: 24
Accepted

Dependency #1:

100%
Accepted

Test #25:

score: 24
Accepted
time: 3ms
memory: 34276kb

input:

3000 1500
1639 2173
2404 1870
1283 985
2883 2977
707 1329
2113 636
2806 2624
298 1064
2713 2778
1794 1869
1414 707
123 438
2461 1887
1110 2119
1348 508
2262 230
1447 938
730 421
328 2137
323 2423
2777 2620
2884 2449
638 662
2399 1045
1371 1573
2756 1439
2580 622
13 2700
1415 997
1276 83
480 30
413 2...

output:

130

result:

ok single line: '130'

Test #26:

score: 0
Accepted
time: 4ms
memory: 35208kb

input:

3000 2999
307 2061
703 217
101 1823
2902 2612
784 2034
2721 2411
1613 746
2392 33
2494 2005
2428 1620
2075 677
97 581
1813 2279
468 565
1348 801
117 2390
2392 2869
1176 1082
2775 2376
1759 51
1752 2287
2021 612
1496 2060
15 2805
1006 1517
2800 2233
1761 2915
296 2685
452 2544
2725 269
347 986
2939 3...

output:

752

result:

ok single line: '752'

Test #27:

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

input:

3000 3000
2725 1595
723 2127
2393 2347
2750 1233
2698 712
1945 2185
503 2913
2570 1227
2785 2988
162 2017
136 1123
552 1429
1687 911
1024 1167
2594 2913
973 1610
1360 1514
1755 642
972 2012
1446 2808
1067 235
778 270
1344 837
287 2368
1830 1637
1053 1167
849 293
2297 408
2050 1513
303 1455
238 2153
...

output:

752

result:

ok single line: '752'

Test #28:

score: 0
Accepted
time: 4ms
memory: 34108kb

input:

3000 1500
1415 1514
2797 1358
2227 2849
205 21
745 2988
2296 24
2485 2372
988 1941
398 2864
2277 2344
2911 132
1657 708
259 536
1844 2481
913 478
2883 2850
2176 39
1191 707
1376 2103
771 777
27 2542
2495 2675
935 158
397 1794
199 1988
2967 1282
1340 826
416 1971
1753 2627
2717 2104
1347 1503
1003 22...

output:

142

result:

ok single line: '142'

Test #29:

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

input:

3000 200
2198 2019
798 2298
1651 814
2201 2323
789 2793
2212 1892
2222 376
597 1083
166 1578
958 2866
2857 2620
730 2246
2666 288
2851 586
881 2985
262 1792
1547 1928
63 2708
1550 1479
70 23
1055 1737
1302 2990
2556 2383
54 2650
2355 1661
1312 1628
98 2013
1982 756
363 859
580 1926
2889 175
805 694
...

output:

1

result:

ok single line: '1'

Test #30:

score: 0
Accepted
time: 9ms
memory: 34896kb

input:

3000 2998
1750 681
266 1411
2887 2648
413 933
1162 1514
16 1731
1719 787
2196 2450
1597 975
1286 2696
1689 621
309 941
289 1920
1102 355
1401 1923
2246 1592
2516 163
2778 1929
2003 2586
2937 2263
1803 2313
536 319
2247 2664
2019 1439
2518 70
1428 309
1601 2206
2810 2371
230 2871
2581 2162
200 2590
4...

output:

1

result:

ok single line: '1'

Test #31:

score: 0
Accepted
time: 4ms
memory: 34100kb

input:

3000 2900
29 1226
1147 2408
2447 1537
2124 2466
165 423
92 448
175 2871
1323 1429
2062 2763
1617 1953
896 2729
2990 1032
2785 1874
2345 322
1571 1591
2313 2009
2242 2648
1900 2560
1540 1612
1463 137
2173 240
1663 32
2480 383
1977 1707
1432 2464
2367 2066
1903 1812
2589 2221
143 2597
2459 1376
2568 5...

output:

9

result:

ok single line: '9'

Test #32:

score: 0
Accepted
time: 4ms
memory: 34340kb

input:

3000 2997
1889 2385
451 85
2501 104
1553 1047
836 2857
166 908
2281 222
2404 2810
2231 2355
1523 387
439 2329
1750 2767
2013 1671
1389 2092
990 2138
2171 2639
1840 1943
1216 1594
433 15
945 350
922 1411
1421 2539
1968 2900
1388 804
1660 1579
118 1906
2639 851
2894 1688
1284 2406
2450 342
1185 387
29...

output:

748

result:

ok single line: '748'

Test #33:

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

input:

3000 50
1695 2272
1660 330
2330 688
1648 2997
2064 153
2158 1851
2025 2285
846 2822
526 208
615 250
1815 1897
974 1882
2142 2416
515 804
1803 784
297 1474
3000 2998
775 2315
1902 2314
451 496
2587 268
978 2900
2557 995
1935 1471
2015 2156
21 2775
739 148
1818 2720
2403 1339
980 1768
1206 2730
2058 1...

output:

0

result:

ok single line: '0'

Test #34:

score: 0
Accepted
time: 4ms
memory: 35160kb

input:

3000 1
1653 1116
2985 613
512 1295
2122 469
1771 2673
1397 1624
378 2541
184 2490
484 2560
179 1116
1365 1159
2007 445
527 174
351 523
598 2685
1562 2906
2600 456
2829 2826
1898 2167
340 1033
424 595
669 1978
649 749
1147 984
2364 1151
11 2333
703 2229
2923 2040
957 911
809 352
639 825
584 1309
2586...

output:

0

result:

ok single line: '0'

Test #35:

score: 0
Accepted
time: 4ms
memory: 34420kb

input:

3000 10
1473 1807
1415 1474
2762 1661
1708 1733
598 1792
2066 264
2777 2556
1305 2929
2962 1632
2031 2888
1059 1446
2464 2248
1854 2680
2970 1092
13 928
2541 398
212 1420
934 2448
1184 67
2625 2817
2375 1116
2902 1707
548 2186
1644 1370
723 868
280 938
1083 1397
2792 98
1732 2380
1260 2265
2084 1815...

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 4ms
memory: 34688kb

input:

3000 1
919 1683
2424 1410
468 2633
970 2533
432 2100
2874 71
38 1204
1284 1644
1963 2947
2942 1909
1507 2139
612 998
2326 409
2379 1938
2452 1341
216 1997
1168 1652
134 2302
1356 2655
2880 1716
2338 700
2215 896
1849 2557
474 1300
2858 1864
2357 2821
1067 518
564 943
1000 1460
2165 1628
1323 1050
23...

output:

0

result:

ok single line: '0'

Test #37:

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

input:

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

output:

13

result:

ok single line: '13'

Test #38:

score: 0
Accepted
time: 3ms
memory: 33264kb

input:

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

output:

13

result:

ok single line: '13'

Test #39:

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

input:

100 50
84 57
63 12
55 17
96 99
54 43
42 64
36 52
53 6
67 26
43 77
3 50
71 15
49 65
79 52
55 84
61 70
5 48
79 100
86 73
83 44
39 97
89 33
51 47
14 43
11 3
74 87
86 68
12 89
98 94
88 64
11 25
80 24
92 64
5 96
69 19
55 23
83 52
20 76
98 47
58 48
19 72
6 70
58 80
10 54
50 94
56 38
53 7
1 5
71 80
10 50
3...

output:

4

result:

ok single line: '4'

Test #40:

score: 0
Accepted
time: 5ms
memory: 34320kb

input:

3000 50
228 492
1373 2420
1265 704
1391 1394
2327 2134
1710 1537
2114 1512
2080 2973
1285 2440
869 2027
325 2764
428 1317
2237 1721
715 2026
2620 389
2783 1972
1320 1438
1646 1610
2828 829
96 2979
1471 254
961 2975
315 2562
1308 2843
2650 1128
732 1233
2455 761
1090 994
161 394
1332 1740
2092 145
48...

output:

13

result:

ok single line: '13'

Test #41:

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

input:

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

output:

1

result:

ok single line: '1'

Test #42:

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

input:

3000 50
1332 2737
2322 2387
2844 2837
913 1982
669 2550
1310 2897
472 1577
2974 469
2137 885
2317 1599
442 1058
2147 2480
1225 1860
2119 1865
727 1170
1749 2419
1479 2335
552 1814
1770 2698
1081 1863
1817 2000
2848 795
2133 2345
1928 343
845 2099
2427 2665
2480 213
2309 1352
1909 1650
1469 358
211 1...

output:

14

result:

ok single line: '14'

Test #43:

score: 0
Accepted
time: 4ms
memory: 34952kb

input:

3000 50
921 33
921 1227
921 1131
921 1189
921 1107
921 1080
2084 921
921 2212
1561 921
793 921
2407 921
921 369
921 1405
548 921
1415 921
1773 921
1991 921
1435 921
2923 921
921 168
1007 921
921 2257
921 1705
552 921
2060 921
921 2696
921 1339
1039 921
921 2370
499 921
2666 921
921 1156
1776 921
921...

output:

0

result:

ok single line: '0'

Test #44:

score: 0
Accepted
time: 3ms
memory: 34068kb

input:

3000 50
2085 1957
2857 2085
2085 200
2085 927
2085 1011
2085 2238
2714 1094
2373 2085
2305 2085
2076 1094
1717 2085
2244 1094
2517 2085
498 1094
1094 2837
2085 825
1094 1653
2085 2549
102 2085
1094 205
1094 1570
670 1094
1094 198
1094 2195
1447 2085
2085 1970
2150 1094
2836 1094
1094 983
857 2085
10...

output:

0

result:

ok single line: '0'

Test #45:

score: 0
Accepted
time: 3ms
memory: 34712kb

input:

100 98
14 78
42 73
7 45
93 92
100 2
20 76
25 36
85 12
71 90
48 82
82 66
66 64
39 46
12 34
82 9
99 66
81 30
87 53
33 59
3 15
42 63
78 64
24 89
77 45
89 56
82 73
15 18
57 75
6 22
25 33
1 54
72 57
48 84
17 34
61 2
50 69
85 62
90 73
96 78
59 27
33 76
70 69
60 31
53 82
41 74
80 86
1 73
30 69
8 25
44 30
1...

output:

26

result:

ok single line: '26'

Test #46:

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

input:

3000 600
1929 1763
842 1548
708 2126
783 1626
1429 2800
2036 2873
2223 668
315 2739
2208 1004
1589 1082
12 203
2363 677
925 2962
2782 1324
2048 1546
561 1407
1976 1964
934 246
1971 556
978 1295
950 2856
2084 2209
1163 1832
2140 2153
268 1697
1476 2384
2946 536
1270 2144
563 2534
1823 560
727 1683
16...

output:

76

result:

ok single line: '76'

Test #47:

score: 0
Accepted
time: 9ms
memory: 34092kb

input:

2970 1485
920 238
123 2291
1514 295
2958 715
1739 718
2204 1769
1808 1670
1761 2837
904 2020
2677 2671
1751 1808
2085 2199
151 76
948 1678
913 1206
2874 2117
1219 1992
1513 1788
2730 2081
1504 921
798 2612
2082 1058
305 2946
2431 745
201 2742
1431 1707
1027 1657
1940 1965
1993 2642
2882 2526
2124 15...

output:

142

result:

ok single line: '142'

Test #48:

score: 0
Accepted
time: 4ms
memory: 34584kb

input:

3000 2000
513 1645
1497 383
1127 2710
538 996
1169 1094
1152 33
2039 2605
1171 690
2740 713
1294 418
941 588
1949 1647
306 1532
2435 653
205 2758
113 992
1055 2947
1783 1050
1891 1711
509 1841
964 134
556 498
1112 818
680 1540
2130 469
2137 272
1014 1286
2721 2964
547 812
2111 530
218 15
525 129
229...

output:

308

result:

ok single line: '308'

Test #49:

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

input:

100 70
52 6
35 66
50 59
23 40
97 65
98 66
75 44
3 34
73 93
19 63
2 74
48 21
20 64
77 62
90 78
38 13
53 63
63 58
79 12
44 84
27 84
46 60
72 81
76 96
27 91
92 54
42 86
13 60
1 37
67 6
19 92
32 39
70 21
48 16
86 23
47 100
48 49
1 32
85 29
84 74
24 82
15 47
78 18
79 56
26 2
17 4
8 3
83 76
45 61
21 43
7 ...

output:

7

result:

ok single line: '7'

Test #50:

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

input:

3000 600
2784 2734
306 1837
2361 2818
642 2393
669 1856
2038 2058
2541 45
1805 463
932 288
2018 1244
2812 314
668 1169
2851 2647
2237 1304
322 2247
1340 136
2139 663
2932 593
50 1710
986 2823
1336 102
47 1423
132 1031
1346 660
472 2364
2771 2286
2549 2268
1810 2379
1590 1473
1966 1822
166 2707
2329 ...

output:

78

result:

ok single line: '78'

Test #51:

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

input:

3000 1500
1569 1758
1569 997
1569 2409
384 1569
1569 1093
326 1569
2354 1569
1569 2971
1079 1569
2757 1569
2745 1569
658 1569
1569 1688
927 1569
2199 1569
1569 1838
1569 2911
1569 2541
1569 686
1569 1886
1569 2147
1569 2856
1853 1569
2109 1569
1569 466
1569 106
1218 1569
1569 2261
23 1569
1691 1569
...

output:

276

result:

ok single line: '276'

Test #52:

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

input:

3000 3000
1985 2838
2489 1985
1985 2912
285 1985
1985 2921
1985 2414
2031 1985
1985 2994
1731 1985
1978 1985
2654 1985
1985 1697
1490 1985
2341 1985
1985 2631
1800 1985
2813 1985
2409 1985
1897 1985
1346 1985
1985 94
143 1985
1985 1021
1985 502
1985 1687
1985 860
1685 1985
1985 1899
1080 1985
1985 6...

output:

1500

result:

ok single line: '1500'

Test #53:

score: 0
Accepted
time: 8ms
memory: 34844kb

input:

3000 1500
1177 982
2368 1174
1174 755
531 982
622 1174
982 2110
1174 1089
1174 1129
1174 155
2728 1174
1174 1055
982 1767
1174 1537
1174 2437
1174 2805
876 1174
1174 812
982 2371
875 1174
2994 1174
1174 1732
1174 2264
982 2045
1174 2301
982 897
982 2667
122 982
1174 2435
1174 800
2285 982
1174 1327
...

output:

277

result:

ok single line: '277'

Test #54:

score: 0
Accepted
time: 8ms
memory: 32564kb

input:

3000 3000
2635 1889
1582 1845
94 1782
2480 468
2035 2925
888 770
764 2352
1890 2934
1445 2487
2443 2942
666 2091
2570 1944
1018 2055
2365 1751
702 723
1969 445
1457 2546
846 2967
43 1939
1139 2396
1607 2565
2603 1820
2708 2245
539 2593
29 426
995 416
465 1466
2556 1073
30 2885
1172 2965
1758 1118
23...

output:

750

result:

ok single line: '750'

Subtask #3:

score: 14
Accepted

Dependency #2:

100%
Accepted

Test #55:

score: 14
Accepted
time: 46ms
memory: 46916kb

input:

100000 1
29360 96086
69686 55148
89841 34262
36276 37294
5716 58629
50737 90809
82138 89842
94284 78694
26604 44074
46636 14788
33586 84318
42429 94371
48998 37425
58745 49272
20379 45724
16720 15816
62728 69764
94674 91726
95723 76713
34265 14675
18236 60739
20735 6523
45179 28544
362 65646
55986 8...

output:

0

result:

ok single line: '0'

Test #56:

score: 0
Accepted
time: 46ms
memory: 47188kb

input:

100000 50
78656 588
85179 92907
82759 14729
71025 37723
84638 88744
12148 92058
75660 49959
12212 44974
60831 48537
61802 73466
62004 71190
67898 82289
35506 92441
73661 35172
7917 78292
54851 42522
7489 90316
49994 56030
79125 37217
69621 31750
46720 43066
17566 8489
91101 47453
526 64230
49511 407...

output:

0

result:

ok single line: '0'

Test #57:

score: 0
Accepted
time: 48ms
memory: 45728kb

input:

100000 50
79401 55371
63506 3770
41781 90832
37223 77928
57593 84780
73085 37751
5062 61363
98283 4520
96554 2650
57168 62696
18920 89271
51169 1848
93627 78264
36323 13193
82660 96463
2549 91425
19579 89821
12662 92540
5564 59746
90226 37282
18207 13416
90110 37025
70097 91475
79309 71024
21265 375...

output:

13

result:

ok single line: '13'

Test #58:

score: 0
Accepted
time: 54ms
memory: 47292kb

input:

100000 50
19044 41326
64 56733
15243 92738
93007 51892
57565 86648
50335 99988
22096 42355
57195 59126
67107 84084
59650 22282
12950 77777
34376 53326
4351 31653
99939 20891
68990 62937
74426 15468
39498 49887
75720 49899
82603 97388
83820 8290
93867 81502
9096 48888
6167 13864
84627 52622
78204 582...

output:

1

result:

ok single line: '1'

Test #59:

score: 0
Accepted
time: 46ms
memory: 50708kb

input:

100000 1
21485 72671
36839 12448
40692 88592
63505 16760
19299 38917
88474 89900
3716 59017
43677 82728
10774 9612
34293 21116
99159 93021
25902 67695
94539 12777
7525 73061
57225 30228
2644 93186
81213 17888
3644 65205
61907 54676
73677 10319
5963 59412
88020 99966
11873 48750
90308 70443
39684 109...

output:

0

result:

ok single line: '0'

Test #60:

score: 0
Accepted
time: 65ms
memory: 50640kb

input:

100000 50
50058 69626
50136 66540
37246 320
85119 1097
61037 34306
58057 16331
77868 71585
85192 2140
80880 68156
31226 97786
93421 67935
81162 57341
44921 90475
79520 3075
86802 67333
32763 93151
60483 85358
5706 87475
50422 90269
2033 37487
68419 60269
65705 37721
36709 46626
27111 35559
47197 116...

output:

0

result:

ok single line: '0'

Test #61:

score: 0
Accepted
time: 61ms
memory: 43904kb

input:

100000 50
82899 96671
74288 43309
5327 78110
79211 13834
32641 59081
63775 53206
72934 17442
88120 47957
90258 60344
86179 22317
92152 18372
41333 89174
42860 76777
65089 56262
94250 38346
10963 99845
98762 77475
537 73016
30881 29743
1604 57998
67863 50083
43743 14848
35113 20192
21247 45700
11020 ...

output:

14

result:

ok single line: '14'

Test #62:

score: 0
Accepted
time: 78ms
memory: 47416kb

input:

100000 50
78093 95618
72222 82951
17123 79723
53730 60442
55663 38650
55105 70860
63787 97204
16952 69877
77345 1586
77422 88566
57387 58708
84146 49452
53042 58221
47923 32332
98646 62988
47829 20636
58839 30721
90834 98886
14153 54941
76480 82671
40241 56974
6907 31833
92846 93134
74356 68970
9524...

output:

1

result:

ok single line: '1'

Test #63:

score: 0
Accepted
time: 55ms
memory: 48628kb

input:

100000 50
88408 53621
73434 16747
11452 74335
50468 98137
18747 64874
49315 88894
8824 64851
7286 68551
34109 18053
62129 58013
76540 6459
11889 99485
52441 15359
91098 47962
16862 6844
78221 51162
70749 77759
14304 93895
51643 5851
10022 56145
73056 48733
70572 63922
19834 92441
29147 50363
57099 3...

output:

0

result:

ok single line: '0'

Test #64:

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

input:

100000 50
95890 73624
95890 66778
95890 33019
46000 95890
39653 95890
95890 36275
79445 95890
95890 51764
63301 95890
95890 47549
95890 2419
95890 6347
49475 95890
6517 95890
41242 95890
95890 84548
95890 23324
95890 61696
74592 95890
95890 84272
95890 87991
17305 95890
95890 29632
95890 68107
49578...

output:

0

result:

ok single line: '0'

Test #65:

score: 0
Accepted
time: 41ms
memory: 43856kb

input:

100000 50
8837 3182
3182 19851
88350 94571
67974 3182
71510 94571
13892 94571
3182 27798
3182 27853
94571 95041
3182 28140
29062 94571
22681 3182
94571 5892
94571 67459
8817 3182
3182 62802
58129 3182
97157 3182
55486 94571
3182 76992
3182 7048
18144 94571
94571 74842
94571 42650
3182 59030
94571 41...

output:

0

result:

ok single line: '0'

Subtask #4:

score: 22
Accepted

Test #66:

score: 22
Accepted
time: 49ms
memory: 50336kb

input:

100000 100000
14957 4585
67467 70858
61843 47396
50630 17382
61027 39858
94990 21698
10240 22940
23505 67581
91432 14182
22040 40125
24556 60351
75822 41519
82801 23601
90653 29138
85096 34582
99587 59109
8932 45189
18235 36632
43160 14939
67600 76675
60175 65542
99294 53955
46429 66931
16822 48854
...

output:

25042

result:

ok single line: '25042'

Test #67:

score: 0
Accepted
time: 60ms
memory: 47764kb

input:

100000 50000
3065 28396
57666 99424
91431 92279
85107 9397
40557 2609
33754 76986
41982 13262
29268 57814
57080 70949
46008 55628
16881 69517
7925 97656
11194 27261
1023 44957
63053 94265
10347 36227
57858 50853
6707 37237
14023 64077
97278 89836
45448 37054
47530 12666
1789 54939
97196 38225
46942 ...

output:

4686

result:

ok single line: '4686'

Test #68:

score: 0
Accepted
time: 62ms
memory: 44356kb

input:

100000 1000
15892 97873
74044 8515
2591 62904
30957 88449
38848 47109
51265 48273
55368 54375
67431 61662
74306 32695
87126 54432
72682 57299
66802 28200
3201 72387
26153 31276
44001 47337
27981 6477
15995 26102
90218 8030
97876 99025
38725 79748
61045 12996
27173 63491
31237 7298
64134 63770
59955 ...

output:

252

result:

ok single line: '252'

Test #69:

score: 0
Accepted
time: 60ms
memory: 45432kb

input:

100000 50000
33160 23295
28957 34869
60520 32863
7862 68797
48379 81124
95012 36902
86480 11178
89023 90581
98753 45510
95 163
50395 60900
89762 36279
56185 22354
15359 97979
61728 37941
68183 27192
52885 40031
54463 33490
22324 25911
44115 5401
62127 25301
91088 99953
1770 73224
78624 45860
87886 2...

output:

4466

result:

ok single line: '4466'

Test #70:

score: 0
Accepted
time: 57ms
memory: 50896kb

input:

100000 100000
55749 64307
73914 18165
55104 67680
34976 24633
3159 10270
97438 41767
63073 69455
57888 71630
93066 38126
39516 27458
45215 74459
19402 17568
91414 23901
84838 44332
86229 23656
41101 30330
35829 54890
34576 52494
61355 23809
68784 29220
60951 22840
14091 80771
98672 67030
55873 80581...

output:

1

result:

ok single line: '1'

Test #71:

score: 0
Accepted
time: 53ms
memory: 47784kb

input:

100000 10000
30268 39315
46960 33279
28973 55390
22427 61537
60481 79337
30617 20845
59764 27962
17169 39537
65704 18355
51311 86246
34879 31926
90444 83548
94519 80339
98171 79780
79228 94164
91379 44847
97383 90313
45917 64737
22007 66486
49018 7172
90191 31105
80577 48727
26092 3821
9302 17496
60...

output:

2509

result:

ok single line: '2509'

Test #72:

score: 0
Accepted
time: 63ms
memory: 46856kb

input:

100000 1000
11983 6879
71457 57412
57580 56139
50216 34933
12061 84340
23054 62561
94774 46880
55255 30380
38271 57910
59277 70810
80275 32460
39997 11027
70416 43264
1617 86814
15261 89577
12622 88741
16344 80224
10682 4096
73248 12167
99850 50822
16526 23109
40141 86110
91267 35155
16588 24615
385...

output:

250

result:

ok single line: '250'

Test #73:

score: 0
Accepted
time: 44ms
memory: 45180kb

input:

100000 50000
1644 78388
28413 1644
1644 85336
34228 1644
1644 17492
44196 1644
1644 81781
1644 48872
1644 13725
1644 11683
1644 81789
1644 331
88941 1644
24119 1644
16646 1644
28572 1644
1644 86432
1644 65072
51344 1644
82782 1644
1644 29259
1644 55827
82183 1644
1644 51814
1644 61332
23306 1644
164...

output:

9226

result:

ok single line: '9226'

Test #74:

score: 0
Accepted
time: 36ms
memory: 47304kb

input:

100000 100000
75311 62863
12992 62863
62863 84650
62863 51354
62863 26895
62863 45506
73949 62863
52325 62863
82731 62863
62863 69152
62863 90856
32788 62863
55788 62863
62863 27200
62863 57738
62863 31
62863 23706
62863 66045
56818 62863
62863 67848
62863 29291
62863 76276
62863 64266
73 62863
2299...

output:

50000

result:

ok single line: '50000'

Test #75:

score: 0
Accepted
time: 39ms
memory: 49248kb

input:

100000 90000
19476 60409
19476 25028
19476 34083
19476 54697
12041 19476
4002 19476
61428 18220
63240 18220
26989 19476
19476 71157
19476 4783
73741 19476
53048 18220
19476 4739
19476 47478
19476 93934
77399 18220
44691 19476
19476 51884
18220 90022
64398 18220
19476 266
19476 83366
3710 19476
43987...

output:

40276

result:

ok single line: '40276'

Test #76:

score: 0
Accepted
time: 55ms
memory: 50028kb

input:

100000 100000
71299 25937
59932 70939
28364 90446
89661 5153
60103 26078
41297 2486
98016 87305
96050 78768
79662 75090
43520 13402
33038 95170
4444 47166
13055 63932
12489 39142
81784 80513
82508 71507
10719 63574
48479 99586
65578 4080
45399 45226
2399 31001
69289 98218
56702 1990
32214 65821
323 ...

output:

25000

result:

ok single line: '25000'

Subtask #5:

score: 30
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #77:

score: 30
Accepted
time: 283ms
memory: 91172kb

input:

500000 1
122625 36805
118056 234363
294353 39995
392559 248439
461323 139711
289644 8161
469274 96849
69146 143245
440207 266599
139322 358870
125137 128289
489792 415152
273385 304942
457250 337596
232861 306442
435705 26369
281823 333863
269492 235338
51885 246999
304697 349868
383276 473737
44240...

output:

0

result:

ok single line: '0'

Test #78:

score: 0
Accepted
time: 417ms
memory: 99592kb

input:

500000 300000
57219 166038
6779 13384
482623 8366
274359 132605
98696 468448
42970 63513
44310 364835
43706 99403
337872 72582
7735 52679
469031 445764
341297 167079
102599 281896
306776 363013
11401 437006
302492 484025
112792 389709
436047 188072
201186 431076
424662 193045
499628 304874
132001 40...

output:

38613

result:

ok single line: '38613'

Test #79:

score: 0
Accepted
time: 391ms
memory: 105840kb

input:

500000 499900
385456 244811
239555 131788
499272 478306
374431 174216
127035 190799
343861 221967
142565 279238
12169 24656
249759 27032
404714 447820
65193 385964
297075 296102
177694 208284
59967 230935
365203 434916
28604 203217
253051 170297
154519 92174
360139 388112
370378 233760
14664 167555
...

output:

124914

result:

ok single line: '124914'

Test #80:

score: 0
Accepted
time: 383ms
memory: 106000kb

input:

500000 499999
467804 494683
318365 407363
342019 471232
404369 320837
424628 85653
342920 181372
40240 191206
456355 130294
331073 282050
109174 396722
365829 144169
456866 429773
14592 483084
317490 6585
200747 116127
1859 382435
405847 203722
369811 118598
81223 384206
338835 330622
113191 28266
3...

output:

124910

result:

ok single line: '124910'

Test #81:

score: 0
Accepted
time: 388ms
memory: 105752kb

input:

500000 500000
32896 494277
27449 75285
204608 469312
341984 166496
125941 39401
238315 195486
450208 82206
440788 251770
233212 243750
326195 201928
193907 210507
353518 424885
468791 55306
189123 261822
160262 409472
444807 461686
22351 269054
316464 34586
383369 220162
358327 289401
368720 323220
...

output:

124901

result:

ok single line: '124901'

Test #82:

score: 0
Accepted
time: 372ms
memory: 90604kb

input:

500000 2
71340 75786
342921 175941
140657 226112
114459 477329
280067 398467
197636 92639
260846 210831
354888 315089
460919 92948
160904 160266
159413 346964
202441 443932
70943 50657
471759 412879
414601 290109
90141 178219
480340 427631
482487 211588
482425 291584
476846 15842
435091 261773
43073...

output:

1

result:

ok single line: '1'

Test #83:

score: 0
Accepted
time: 478ms
memory: 95180kb

input:

500000 100000
45275 59197
235600 439804
44388 232459
15939 425669
468474 55849
411843 271295
47381 19647
98696 413156
488715 133716
129046 438015
127255 387832
317586 240359
350460 270979
476336 291024
158971 3330
128509 131667
4995 452921
199934 455998
73879 173635
472735 6073
396991 265973
324083 ...

output:

468

result:

ok single line: '468'

Test #84:

score: 0
Accepted
time: 379ms
memory: 92888kb

input:

490000 700
351012 147840
115488 89791
29202 159371
132159 240043
195231 74249
150967 278578
189840 294493
395625 193480
248034 201383
433738 217081
456288 161798
277203 228627
41202 96998
339805 301981
248504 343475
477633 186991
137324 411955
330187 392129
188804 457901
448886 387463
378111 229966
...

output:

177

result:

ok single line: '177'

Test #85:

score: 0
Accepted
time: 529ms
memory: 108992kb

input:

500000 1
160422 400435
100340 183513
156603 443668
25786 481220
38194 158943
485320 173928
87960 271978
432663 303063
227031 223326
331686 134339
329841 302004
106377 197054
493480 105325
224703 441862
264294 327333
259113 297084
432113 124068
305469 173293
251554 141786
160528 432254
207738 263389
...

output:

0

result:

ok single line: '0'

Test #86:

score: 0
Accepted
time: 518ms
memory: 119336kb

input:

500000 499999
426568 458327
50096 294482
327146 39584
89259 384222
77157 337131
288908 48303
423494 62520
131082 86898
471670 158860
223691 107534
390791 11046
305543 431354
495504 10690
71416 383819
218713 396972
190111 173710
308642 416922
450310 282310
482501 197674
472820 335670
160839 140505
18...

output:

1

result:

ok single line: '1'

Test #87:

score: 0
Accepted
time: 562ms
memory: 101344kb

input:

500000 2
401100 215161
490119 426556
111276 192252
154144 407613
204714 442884
296869 227703
13225 109290
453778 82178
292940 367373
110288 482947
369896 133551
66767 323752
168111 45786
121124 478153
128177 124715
440293 410707
285676 417979
469397 396435
335770 477970
102203 193158
78743 397166
46...

output:

1

result:

ok single line: '1'

Test #88:

score: 0
Accepted
time: 483ms
memory: 104848kb

input:

490000 489300
55664 343438
28750 419150
131065 100021
130565 10772
203029 50496
337090 474712
408422 323142
155612 228899
128272 275868
464600 366338
155776 283286
389540 378239
211433 118576
136553 415686
28967 184132
301575 125091
489726 234439
456848 172676
289661 46683
391499 90664
270113 337886...

output:

695

result:

ok single line: '695'

Test #89:

score: 0
Accepted
time: 296ms
memory: 97384kb

input:

500000 200000
432967 313771
134068 313771
313771 213651
132195 313771
159743 313771
313771 319872
17137 313771
313771 467717
409874 313771
313771 59447
136966 313771
107134 313771
313771 405112
313771 392857
313771 316198
313771 471777
313771 111896
313771 475124
313771 178003
313771 292467
313771 4...

output:

22422

result:

ok single line: '22422'

Test #90:

score: 0
Accepted
time: 231ms
memory: 104872kb

input:

500000 500000
147938 114690
147938 145653
147938 44706
147938 305095
343073 147938
147938 331282
147938 374107
147938 263576
147938 36577
187410 147938
264743 147938
147938 344849
474688 147938
147938 410441
147938 131602
392312 147938
130546 147938
147938 81614
147938 493452
147938 144004
11248 147...

output:

250000

result:

ok single line: '250000'

Test #91:

score: 0
Accepted
time: 253ms
memory: 105004kb

input:

500000 450000
451437 306225
389440 451437
391693 451437
451437 85767
107312 469917
451437 96491
451437 265276
498572 451437
426247 107312
107312 288405
451437 339858
142894 451437
107312 477666
451437 228838
451437 357732
472384 107312
107312 124892
328837 451437
257248 107312
215313 107312
451437 1...

output:

201313

result:

ok single line: '201313'

Test #92:

score: 0
Accepted
time: 401ms
memory: 113724kb

input:

500000 499990
5156 80879
106933 19263
353626 147259
434204 440421
72494 86330
433568 175959
498469 281278
449854 211904
168243 122619
126515 345475
373750 79662
296414 397427
303407 375618
26645 469119
284743 173857
171245 217933
98888 459502
25583 228018
3582 363216
456108 146322
135768 67376
23365...

output:

124995

result:

ok single line: '124995'

Test #93:

score: 0
Accepted
time: 449ms
memory: 113972kb

input:

500000 500000
435851 114279
463175 49587
105915 106434
4666 416907
421022 376340
472473 393222
348738 77190
410773 425285
371228 274383
499856 153025
268372 297396
249714 279157
165897 357302
372410 474471
341991 48806
355637 425119
395373 345687
357246 394225
301880 72741
441895 50381
326136 274312...

output:

125000

result:

ok single line: '125000'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

Server Time: 2025-01-20 06:01:20 | OpenSource Project