oj.uz

Submission #236295

# Submission time Handle Problem Language Result Execution time Memory
236295 2020-06-01T02:11:29 Z super_j6 Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 990 ms 174588 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
const int maxn = 1000000;
int n, m, k;
int a[maxn], d[maxn], dp[maxn];
vector<int> graph[maxn];
vector<pi> v;
 
void dfs(int c, int p){
	pi ret;
 	for(int i : graph[c]){
		if(i == p) continue;
		if(~p) dp[i] += dp[c] + graph[c].size() - 2;
		dfs(i, c);
		a[c] |= a[i];
		ret.s = max(ret.s, dp[i]);
		if(ret.s > ret.f) swap(ret.f, ret.s);
	}
	if(graph[c].size() > 2) dp[c] = ret.s;
	dp[c] += graph[c].size() > 1;
}
 
void dfs2(int c, int p){
	if(c == m) return;
	for(int i : graph[c]){
		if(i == p) continue;
		d[i] = d[c] + 1;
		dfs2(i, c);
		if(a[c] && !a[i]) v.push_back({d[i], dp[i] + (c == k)});
	}
}
 
bool works(int x){
	int ret = 0;
	for(pi i : v){
		if(ret > i.f) return 0;
		ret += (i.s + ret) > x;
	}
	return ret <= x;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> k;
	m--, k--;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	
	a[k] = 1, d[k] = -1;
	dfs(m, -1);
	dfs2(k, -1);
	
	sort(v.begin(), v.end());
	
	int l = -1, r = n;
	while(r - l > 1){
		int mid = (l + r) / 2;
		if(works(mid)) r = mid;
		else l = mid;
	}
	
	cout << r << endl;
	
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23680 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 78332 KB Output is correct
2 Correct 369 ms 72908 KB Output is correct
3 Correct 990 ms 81272 KB Output is correct
4 Correct 458 ms 52600 KB Output is correct
5 Correct 982 ms 81372 KB Output is correct
6 Correct 988 ms 81284 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23680 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 18 ms 23984 KB Output is correct
13 Correct 18 ms 23936 KB Output is correct
14 Correct 18 ms 23936 KB Output is correct
15 Correct 18 ms 23936 KB Output is correct
16 Correct 18 ms 23936 KB Output is correct
17 Correct 18 ms 23936 KB Output is correct
18 Correct 18 ms 23936 KB Output is correct
19 Correct 19 ms 23936 KB Output is correct
20 Correct 18 ms 23936 KB Output is correct
21 Correct 18 ms 23856 KB Output is correct
22 Correct 18 ms 23936 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 19 ms 23808 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23680 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 18 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 410 ms 78332 KB Output is correct
12 Correct 369 ms 72908 KB Output is correct
13 Correct 990 ms 81272 KB Output is correct
14 Correct 458 ms 52600 KB Output is correct
15 Correct 982 ms 81372 KB Output is correct
16 Correct 988 ms 81284 KB Output is correct
17 Correct 18 ms 23808 KB Output is correct
18 Correct 18 ms 23984 KB Output is correct
19 Correct 18 ms 23936 KB Output is correct
20 Correct 18 ms 23936 KB Output is correct
21 Correct 18 ms 23936 KB Output is correct
22 Correct 18 ms 23936 KB Output is correct
23 Correct 18 ms 23936 KB Output is correct
24 Correct 18 ms 23936 KB Output is correct
25 Correct 19 ms 23936 KB Output is correct
26 Correct 18 ms 23936 KB Output is correct
27 Correct 18 ms 23856 KB Output is correct
28 Correct 18 ms 23936 KB Output is correct
29 Correct 18 ms 23808 KB Output is correct
30 Correct 481 ms 78392 KB Output is correct
31 Correct 402 ms 78456 KB Output is correct
32 Correct 479 ms 174376 KB Output is correct
33 Correct 490 ms 174588 KB Output is correct
34 Correct 986 ms 81248 KB Output is correct
35 Correct 987 ms 81276 KB Output is correct
36 Correct 984 ms 92916 KB Output is correct
37 Correct 988 ms 93032 KB Output is correct
38 Correct 729 ms 91504 KB Output is correct
39 Correct 742 ms 91636 KB Output is correct
40 Correct 758 ms 91632 KB Output is correct