QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#37353#791. MousetrapMonkeyKing20 145ms71124kbC++2.9kb2022-07-01 11:02:132022-07-01 11:02:15

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:02:15]
  • 评测
  • 测评结果:20
  • 用时:145ms
  • 内存:71124kb
  • [2022-07-01 11:02:13]
  • 提交

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]=min(v[0],v[1]+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: 5ms
memory: 30872kb

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

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

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

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

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

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

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

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

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

input:

2 1 2
1 2

output:

0

result:

ok single line: '0'

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 145ms
memory: 71124kb

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:

38

result:

wrong answer 1st lines differ - expected: '36', found: '38'

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #17:

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

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

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

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

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

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

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: -20
Wrong Answer
time: 4ms
memory: 31048kb

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:

41

result:

wrong answer 1st lines differ - expected: '40', found: '41'

Subtask #4:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%