oj.uz

Submission #161617

# Submission time Handle Problem Language Result Execution time Memory
161617 2019-11-03T10:02:30 Z amoo_safar Mousetrap (CEOI17_mousetrap) C++14
45 / 100
 1442 ms 145716 KB 
#include <bits/stdc++.h>
 
#define pb push_back
#define F first
#define S second
 
using namespace std;
 
typedef long long ll;
typedef string str;
 
const ll Mod = 1e9 + 7;
const int Maxn = 1e6 + 100;

vector<ll> G[Maxn];
ll dp[Maxn], son[Maxn], m1[Maxn], m2[Maxn];
ll t, m;
vector<ll> V;
vector<ll> S[Maxn];
bool DFS(ll u, ll p){
	bool res = (u == m), r2;
	ll cnt = 0;
	ll mx = 0;
	ll mx2 = 0;
	
	for(auto adj : G[u]){
		if(adj == p) continue;
		r2 =DFS(adj, u);
		res |= r2;
		if(!r2){
			S[u].pb(adj);
			cnt ++;
			if(dp[adj] > mx){
				mx2 = mx;
				mx = dp[adj];
			} else mx2 = max(mx2, dp[adj]);
		}
	}
	dp[u] = cnt + mx2;
	m2[u] = mx2;
	m1[u] = mx;
	son[u] = cnt;
	if(res){
		V.pb(u);
	}
	return res;
}
ll dp2[Maxn];
vector< pair<ll, ll> > A;
ll C[Maxn];

bool CMP(ll i, ll j){
	return dp[i] > dp[j];
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n >> t >> m;
	ll u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	DFS(t, -1);
	
	
	ll sz = V.size();
	dp2[sz-1] = 0;
	ll sm = 0;
	for(int i = sz - 2; i >= 0; i--){
		sm += son[V[i]];
		//cerr << son[V[i]] << '\n';
		ll K = 0;
		sort(S[V[i]].begin(), S[V[i]].end(), CMP);
		for(auto ch : S[V[i]]){
			//cerr << '!' << ch << ' ' << dp[ch] << ' ' << sm << '\n';
			A.pb({dp[ch] + sm - K, i + 1});
			K ++;
		}
		
		dp2[i] = min( max(dp2[i + 1], sm-son[V[i]] + m1[V[i]] + son[V[i]]), 1LL + max(dp2[i + 1], sm-son[V[i]] + m2[V[i]] + son[V[i]] - 1) );
		
	}
	sort(A.begin(), A.end()); reverse(A.begin(), A.end());
	ll M = A.size();
	ll cnt = 1;
	//cerr << '\n';
	ll ans = min(dp2[0], (M > 0 ? A[0].F : 1000010));
	bool fl=true;;
	A.pb({0, 0});
	for(int i = 0; i < M; i++){
		for(int j = A[i].S; j <= n; j++){
			C[j] ++;
			if(C[j] > j) fl = false;
		}
		//cerr << i << " " << fl << '\n';
		if(fl) ans = min(ans, i + 1 + A[i + 1].F);
	}
	cout << ans << '\n';
	//cout << dp2[0] << '\n';
	
	
	return 0;
}
/*
5 1 2
1 2
2 3
2 4
3 5

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

7 1 3
1 2
2 3
2 4
4 5
2 6
6 7


*/

Compilation message

mousetrap.cpp: In function 'int main()':
mousetrap.cpp:87:5: warning: unused variable 'cnt' [-Wunused-variable]
  ll cnt = 1;
     ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 50 ms 47392 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47352 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47352 KB Output is correct
7 Correct 49 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 51 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 145716 KB Output is correct
2 Correct 598 ms 134028 KB Output is correct
3 Correct 1401 ms 144852 KB Output is correct
4 Correct 721 ms 97324 KB Output is correct
5 Correct 1409 ms 144852 KB Output is correct
6 Correct 1442 ms 144636 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 50 ms 47392 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47352 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47352 KB Output is correct
7 Correct 49 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 51 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct
11 Incorrect 48 ms 47388 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 47352 KB Output is correct
2 Correct 50 ms 47392 KB Output is correct
3 Correct 49 ms 47352 KB Output is correct
4 Correct 48 ms 47352 KB Output is correct
5 Correct 49 ms 47352 KB Output is correct
6 Correct 49 ms 47352 KB Output is correct
7 Correct 49 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 51 ms 47352 KB Output is correct
10 Correct 48 ms 47352 KB Output is correct
11 Correct 634 ms 145716 KB Output is correct
12 Correct 598 ms 134028 KB Output is correct
13 Correct 1401 ms 144852 KB Output is correct
14 Correct 721 ms 97324 KB Output is correct
15 Correct 1409 ms 144852 KB Output is correct
16 Correct 1442 ms 144636 KB Output is correct
17 Incorrect 48 ms 47388 KB Output isn't correct
18 Halted 0 ms 0 KB -