QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#16518#791. Mousetrapjahayo100 ✓489ms153124kbC++202.3kb2021-12-20 18:29:232022-05-04 09:12:02

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 09:12:02]
  • 评测
  • 测评结果:100
  • 用时:489ms
  • 内存:153124kb
  • [2021-12-20 18:29:23]
  • 提交

answer

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

const int N = 1000010 , inf = 1e8;
int n , B , A;
int head[N] , to[N*2] , nxt[N*2] , cnt;
void addedge(int x , int y) {
	to[++cnt] = y , nxt[cnt] = head[x] , head[x] = cnt;
}

inline int read() {
    int x = 0 ; char c = getchar(); bool f = 0;
    while(c < '0' || c > '9') f |= (c=='-') , c = getchar();
    while(c >= '0' && c <= '9') x = x * 10 + (c^48) , c = getchar();
    return f ? -x : x;
}

int deep[N] , fa[N];
void dfs(int x) {
	for(int i = head[x] ; i ; i = nxt[i]) {
		int y = to[i];
		if(y == fa[x]) continue;
		fa[y] = x , deep[y] = deep[x] + 1 , dfs(y);
	}
}
bool onpath[N] ;
int dp[N];
vector<int> branch[N];

void DP(int x , int top , int sum) {
	if(onpath[x]) top = x;
	int son = 0;
	for(int i = head[x] ; i ; i = nxt[i]) {
		int y = to[i];
		if(y == fa[x]) continue;
		if(son) sum++;
		son++; 
	}
	if(!son) {dp[x] = deep[x] - deep[top] + sum ; return ;}
	
	int maxdp = -inf , max2dp = -inf;
	for(int i = head[x] ; i ; i = nxt[i]) {
		int y = to[i];
		if(y == fa[x]) continue;
		DP(y , top , sum);
		if(dp[y] > maxdp) max2dp = maxdp , maxdp = dp[y];
		else if(dp[y] > max2dp) max2dp = dp[y]; 
	}
	if(son == 1) dp[x] = deep[x] - deep[top] + sum + 1;
	else dp[x] = max2dp;
}

void prepare() {
	n = read() , B = read() , A = read();
	if(A == B) {puts("0"); exit(0);} 
	for(int i = 1 ; i < n ; ++i) {
		int u = read() , v = read();
		addedge(u , v) , addedge(v , u);
	}
	dfs(B);
	for(int p = A ; p != B ; p = fa[p]) onpath[p] = true;
	for(int i = head[B] ; i ; i = nxt[i]) {
		int y = to[i];
		if(onpath[y]) DP(y , y , 0);
	}
	for(int p = A ; p != B ; p = fa[p]) {
		for(int i = head[p] ; i ; i = nxt[i]) {
			int y = to[i];
			if(onpath[y] || y == B) continue;
			branch[p].push_back(dp[y]);
		}
		sort(branch[p].begin() , branch[p].end());
	}
}

bool check(int x) {
	int ban = 0 , id = 0;
	for(int p = A ; p != B ; p = fa[p]) {
		for(int i = 0 ; i < branch[p].size(); ++i)
			if(branch[p][i] + ban > x + (p!=A))
				ban++;
		if(ban > ++id) return false;
	}
	return true;
}

int main() {
//	freopen("fish.in" , "r" , stdin);
//	freopen("fish.out" , "w" , stdout);
	prepare();
	int l = dp[A] , r = 2*n , mid;
	while(l < r) {
		mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n" , l);
	return 0;
}

詳細信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 6ms
memory: 27164kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

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

input:

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

output:

3

result:

ok single line: '3'

Test #3:

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

input:

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

output:

0

result:

ok single line: '0'

Test #4:

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

input:

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

output:

1

result:

ok single line: '1'

Test #5:

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

input:

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

output:

3

result:

ok single line: '3'

Test #6:

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

input:

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

output:

2

result:

ok single line: '2'

Test #7:

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

input:

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

output:

5

result:

ok single line: '5'

Test #8:

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

input:

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

output:

7

result:

ok single line: '7'

Test #9:

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

input:

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

output:

3

result:

ok single line: '3'

Test #10:

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

input:

2 1 2
1 2

output:

0

result:

ok single line: '0'

Subtask #2:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 94ms
memory: 58440kb

input:

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

output:

36

result:

ok single line: '36'

Test #12:

score: 0
Accepted
time: 103ms
memory: 55304kb

input:

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

output:

36

result:

ok single line: '36'

Test #13:

score: 0
Accepted
time: 355ms
memory: 58356kb

input:

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

output:

60

result:

ok single line: '60'

Test #14:

score: 0
Accepted
time: 135ms
memory: 42836kb

input:

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

output:

74

result:

ok single line: '74'

Test #15:

score: 0
Accepted
time: 374ms
memory: 58408kb

input:

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

output:

69

result:

ok single line: '69'

Test #16:

score: 0
Accepted
time: 418ms
memory: 58404kb

input:

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

output:

67

result:

ok single line: '67'

Subtask #3:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 20
Accepted
time: 12ms
memory: 27176kb

input:

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

output:

7

result:

ok single line: '7'

Test #18:

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

input:

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

output:

9

result:

ok single line: '9'

Test #19:

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

input:

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

output:

14

result:

ok single line: '14'

Test #20:

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

input:

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

output:

1

result:

ok single line: '1'

Test #21:

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

input:

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

output:

0

result:

ok single line: '0'

Test #22:

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

input:

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

output:

31

result:

ok single line: '31'

Test #23:

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

input:

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

output:

40

result:

ok single line: '40'

Test #24:

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

input:

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

output:

108

result:

ok single line: '108'

Test #25:

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

input:

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

output:

107

result:

ok single line: '107'

Test #26:

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

input:

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

output:

232

result:

ok single line: '232'

Test #27:

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

input:

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

output:

231

result:

ok single line: '231'

Test #28:

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

input:

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

output:

158

result:

ok single line: '158'

Subtask #4:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #29:

score: 35
Accepted
time: 0ms
memory: 27168kb

input:

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

output:

7

result:

ok single line: '7'

Test #30:

score: 0
Accepted
time: 90ms
memory: 58352kb

input:

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

output:

34

result:

ok single line: '34'

Test #31:

score: 0
Accepted
time: 90ms
memory: 58384kb

input:

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

output:

18

result:

ok single line: '18'

Test #32:

score: 0
Accepted
time: 227ms
memory: 153124kb

input:

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

output:

0

result:

ok single line: '0'

Test #33:

score: 0
Accepted
time: 117ms
memory: 152140kb

input:

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

output:

1

result:

ok single line: '1'

Test #34:

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

input:

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

output:

90

result:

ok single line: '90'

Test #35:

score: 0
Accepted
time: 392ms
memory: 58360kb

input:

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

output:

72

result:

ok single line: '72'

Test #36:

score: 0
Accepted
time: 489ms
memory: 70756kb

input:

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

output:

230404

result:

ok single line: '230404'

Test #37:

score: 0
Accepted
time: 448ms
memory: 70808kb

input:

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

output:

230321

result:

ok single line: '230321'

Test #38:

score: 0
Accepted
time: 456ms
memory: 69860kb

input:

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

output:

100006

result:

ok single line: '100006'

Test #39:

score: 0
Accepted
time: 464ms
memory: 69724kb

input:

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

output:

100001

result:

ok single line: '100001'

Test #40:

score: 0
Accepted
time: 481ms
memory: 69808kb

input:

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

output:

100005

result:

ok single line: '100005'