QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474793#791. Mousetrapfryan#25 362ms72368kbC++201.2kb2024-07-13 04:29:252024-07-13 04:29:26

Judging History

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

  • [2024-07-13 04:29:26]
  • 评测
  • 测评结果:25
  • 用时:362ms
  • 内存:72368kb
  • [2024-07-13 04:29:25]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mxn=1e6+1;

int n,t,m;
vector<int> adj[mxn];
int dp[mxn];

void dfs(int v,int p) {
	auto it=find(all(adj[v]),p);
	if (it!=adj[v].end()) adj[v].erase(it);
	if (!sz(adj[v])) return;
	vector<int> cdp = {0};
 	for (int u:adj[v]) {
		dfs(u,v);
		cdp.push_back(dp[u]);
		sort(all(cdp),greater<int>());
		cdp.resize(2);
	}
	dp[v] = sz(adj[v])+cdp[1];
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	cin>>n>>t>>m;
	for (int i=1; i<n; i++) {
		int u,v; cin>>u>>v; --u; --v;
		adj[u].push_back(v); adj[v].push_back(u);
	}
	dfs(t-1,t-1);
	cout<<dp[m-1]<<"\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3680kb

input:

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

output:

0

result:

wrong answer 1st lines differ - expected: '2', found: '0'

Subtask #2:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 172ms
memory: 70028kb

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

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

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

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

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

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: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%