QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37354#791. MousetrapMonkeyKing100 ✓750ms196036kbC++2.9kb2022-07-01 11:04:082022-07-01 11:04:09

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-01 11:04:09]
  • 评测
  • 测评结果:100
  • 用时:750ms
  • 内存:196036kb
  • [2022-07-01 11:04:08]
  • 提交

answer

#include <bits/stdc++.h>
#define ll long long 
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mp make_pair
#define mt make_tuple
#define ull unsigned long long 
#define rand(l,r) uniform_int_distribution<int>(l,r)(rng)
const int inf=1039714778;
const int mod=1e9+7;
using namespace std;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
template <typename T> inline void chmin(T &x,const T &b) {x=min(x,b);}
template <typename T> inline void chmax(T &x,const T &b) {x=max(x,b);}
inline void chadd(int &x,int b) {x+=b-mod;x+=(x>>31) & mod;}

template <typename T>
ostream & operator << (ostream &cout,const vector<T> &v)
{
	cout<<'{';
	int fst=1;
	for(auto x:v)
	{
		if(fst) fst=0;
		else cout<<',';
		cout<<x;
	}
	cout<<'}';
	return cout;
}

template <typename T1,typename T2>
ostream & operator << (ostream &cout,const pair<T1,T2> &o)
{
	cout<<'('<<o.first<<','<<o.second<<')';
	return cout;
}

namespace FastIO
{
	int cursor=(1<<20);
	char buf[(1<<20)+5];
	char getchar()
	{
		if(cursor==(1<<20))
		{
			cursor=0;
			fread(buf,1,(1<<20),stdin);
		}
		return buf[cursor++];
	}
	int getnum()
	{
		char ch=0;
		int res=0;
		while(!isdigit(ch)) ch=getchar();
		while(isdigit(ch))
		{
			res=res*10+ch-'0';
			ch=getchar();
		}
		return res;
	}
}
using FastIO::getnum;

int n,rt,src;
vector<int> edges[1000005];
int nxt[1000005];
int par[1000005];

void go(int x,int par)
{
	::par[x]=par;
	for(auto u:edges[x])
	{
		if(u==par) continue;
		go(u,x);
	}
}

int dp[1000005];
void dfs(int x,int cost)
{
	for(auto u:edges[x])
	{
		if(u==par[x]) continue;
		dfs(u,cost+(int)edges[x].size()-1-(nxt[x]!=-1));
	}
	if(nxt[x]!=-1) return;
	vector<int> v;
	v.reserve(edges[x].size());
	for(auto u:edges[x])
	{
		if(u!=par[x]) v.emplace_back(dp[u]);
	}
	sort(all(v));
	reverse(all(v));
	if(!v.size())
	{
		dp[x]=cost;
	}
	else if(v.size()==1)
	{
		dp[x]=cost+1;
	}
	else
	{
		dp[x]=v[1];
	}
}

int check(int k)
{
	int rm=0,used=0;
	for(int x=src;x!=rt;x=par[x])
	{
		rm++;
		int cnt=0;
		for(auto u:edges[x])
		{
			if(u==par[x] || u==nxt[x]) continue;
			if(dp[u]+used>k)
			{
				rm--;
				cnt++;
			}
		}
		if(rm<0) return false;
		used+=cnt;
	}
	return (used<=k);
}

int main()
{
	// freopen("input.txt","r",stdin);
	n=getnum();rt=getnum();src=getnum();
	rt--;src--;
	if(rt==src)
	{
		puts("0");
		return 0;
	}
	for(int i=0;i<n-1;i++)
	{
		int x=getnum(),y=getnum();
		x--;y--;
		edges[x].emplace_back(y);
		edges[y].emplace_back(x);
	}
	go(rt,-1);
	memset(nxt,-1,sizeof(nxt));
	int x=src;
	while(x!=rt)
	{
		nxt[par[x]]=x;
		x=par[x];
	}
	dfs(nxt[rt],0);
	int l=0,r=n,mid,res;
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))
		{
			res=mid;
			r=mid-1;
		}
		else
		{
			l=mid+1;
		}
	}
	cout<<res<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

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

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: 2ms
memory: 30892kb

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: 2ms
memory: 30944kb

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: 2ms
memory: 31048kb

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: 11ms
memory: 30944kb

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: 2ms
memory: 30972kb

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: 7ms
memory: 30900kb

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: 6ms
memory: 30972kb

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: 4ms
memory: 30952kb

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: 3ms
memory: 30996kb

input:

2 1 2
1 2

output:

0

result:

ok single line: '0'

Subtask #2:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 127ms
memory: 70912kb

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: 106ms
memory: 67088kb

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: 736ms
memory: 72072kb

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: 298ms
memory: 52000kb

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: 728ms
memory: 72012kb

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: 750ms
memory: 72068kb

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: 6ms
memory: 31056kb

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: 31044kb

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: 5ms
memory: 31016kb

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: 5ms
memory: 31000kb

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: 1ms
memory: 31016kb

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: 2ms
memory: 31024kb

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: 31088kb

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: 2ms
memory: 30948kb

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: 7ms
memory: 31084kb

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: 1ms
memory: 30944kb

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: 9ms
memory: 30940kb

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: 2ms
memory: 30944kb

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: 6ms
memory: 30840kb

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: 145ms
memory: 70972kb

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: 142ms
memory: 70960kb

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: 245ms
memory: 192124kb

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: 183ms
memory: 196036kb

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: 725ms
memory: 72068kb

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: 740ms
memory: 72132kb

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: 719ms
memory: 84164kb

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: 699ms
memory: 84148kb

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: 502ms
memory: 86776kb

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: 499ms
memory: 86804kb

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: 496ms
memory: 86716kb

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'