oj.uz

답안 #585129

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585129 2022-06-28T10:30:56 Z amunduzbaev Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 915 ms 225400 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array
typedef int64_t ll;
//~ #define int ll
 
const int N = 1e6 + 5;
vector<int> edges[N];
int n, t, m, dp[N], is[N];
int c[N];
 
void dfs(int u, int p = -1){
	is[u] = (u == t), c[u] = -1;
	vector<int> t;
	for(auto x : edges[u]){
		if(x == p) continue;
		dfs(x, u);
		is[u] |= is[x];
		if(!is[x]) t.push_back(x);
		else c[u] = x;
	}
	sort(t.begin(), t.end(), [&](int& i, int& j){
		return dp[i] > dp[j];
	});
	edges[u] = t;
	
	if(t.empty()) dp[u] = 0;
	else {
		dp[u] = t.size();
		if((int)t.size() > 1) dp[u] += dp[t[1]]; 
	}
}
 
signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>t>>m;
	if(t == m){
		cout<<0<<"\n";
		return 0;
	}
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dfs(m);
	int tot = 0, u = m;
	vector<int> v;
	while(u != t){
		v.push_back(edges[u].size());
		tot += edges[u].size();
		u = c[u];
	}
	
	for(int i=(int)v.size() - 2;~i;i--){
		v[i] += v[i+1];
	} v.push_back(0);
	auto check = [&](int mx){
		int u = m, pos = 0, prev = 0, in = 0;
		while(u != t){
			pos++;
			int rem = edges[u].size();
			for(auto x : edges[u]){
				if(dp[x] + prev + rem + v[in + 1] > mx) pos--, prev++;
				rem--;
			}
			if(pos < 0) return false;
			u = c[u], in++;
		}
		
		return true;
	};
	
	int l = tot, r = 1e9;
	while(l < r){
		int m = (l + r) >> 1;
		if(check(m)) r = m;
		else l = m + 1;
	}
	
	//~ while(m != t){
		//~ pos++;
		//~ vector<int>& t = edges[m];
		//~ sort(t.begin(), t.end(), [&](int& i, int& j){
			//~ return dp[i] > dp[j];
		//~ });
		
		//~ if(pos >= (int)t.size()){
			//~ pos -= (int)t.size();
			//~ res += (int)t.size();
		//~ } else {
			//~ res += dp[t[pos]] + (int)t.size();
			//~ pos = 1e9;
		//~ }
		//~ m = c[m];
	//~ }
	
	cout<<l<<"\n";
}
 
/*
 
8 7 1
1 2
2 3
3 4
3 5
3 6
4 7
4 8
 
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23720 KB Output is correct
4 Correct 12 ms 23772 KB Output is correct
5 Correct 17 ms 23744 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 13 ms 23820 KB Output is correct
8 Correct 13 ms 23752 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 14 ms 23812 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 312 ms 66776 KB Output is correct
2 Correct 286 ms 63484 KB Output is correct
3 Correct 815 ms 69016 KB Output is correct
4 Correct 344 ms 46912 KB Output is correct
5 Correct 841 ms 68960 KB Output is correct
6 Correct 807 ms 68940 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23720 KB Output is correct
4 Correct 12 ms 23772 KB Output is correct
5 Correct 17 ms 23744 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 13 ms 23820 KB Output is correct
8 Correct 13 ms 23752 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 14 ms 23812 KB Output is correct
11 Correct 13 ms 23764 KB Output is correct
12 Correct 14 ms 23820 KB Output is correct
13 Correct 14 ms 23764 KB Output is correct
14 Correct 13 ms 24020 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 17 ms 23764 KB Output is correct
17 Correct 15 ms 23764 KB Output is correct
18 Correct 15 ms 23808 KB Output is correct
19 Correct 15 ms 23788 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 12 ms 23868 KB Output is correct
22 Correct 12 ms 23800 KB Output is correct

Subtask #4
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 11 ms 23720 KB Output is correct
4 Correct 12 ms 23772 KB Output is correct
5 Correct 17 ms 23744 KB Output is correct
6 Correct 14 ms 23764 KB Output is correct
7 Correct 13 ms 23820 KB Output is correct
8 Correct 13 ms 23752 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 14 ms 23812 KB Output is correct
11 Correct 312 ms 66776 KB Output is correct
12 Correct 286 ms 63484 KB Output is correct
13 Correct 815 ms 69016 KB Output is correct
14 Correct 344 ms 46912 KB Output is correct
15 Correct 841 ms 68960 KB Output is correct
16 Correct 807 ms 68940 KB Output is correct
17 Correct 13 ms 23764 KB Output is correct
18 Correct 14 ms 23820 KB Output is correct
19 Correct 14 ms 23764 KB Output is correct
20 Correct 13 ms 24020 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 17 ms 23764 KB Output is correct
23 Correct 15 ms 23764 KB Output is correct
24 Correct 15 ms 23808 KB Output is correct
25 Correct 15 ms 23788 KB Output is correct
26 Correct 12 ms 23764 KB Output is correct
27 Correct 12 ms 23868 KB Output is correct
28 Correct 12 ms 23800 KB Output is correct
29 Correct 12 ms 23764 KB Output is correct
30 Correct 324 ms 80140 KB Output is correct
31 Correct 335 ms 80092 KB Output is correct
32 Correct 443 ms 225400 KB Output is correct
33 Correct 426 ms 221104 KB Output is correct
34 Correct 788 ms 81128 KB Output is correct
35 Correct 787 ms 81108 KB Output is correct
36 Correct 915 ms 95784 KB Output is correct
37 Correct 896 ms 95772 KB Output is correct
38 Correct 635 ms 98632 KB Output is correct
39 Correct 637 ms 98580 KB Output is correct
40 Correct 723 ms 98612 KB Output is correct