Submission #445732

#	Time	Username	Problem	Language	Result	Execution time	Memory
445732		Nima_Naderi	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1317 ms	249536 KiB

mousetrap

///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 1e6 + 10;
ll n, t, m;
ll dp[MXN], dad[MXN];
ll limb[MXN], deg[MXN];
vector<ll> DpV[MXN], adj[MXN];
bool inp[MXN]; //in path
void prep(ll u){
    inp[u] = (m == u);
    deg[u] = (u == t ? 1 : adj[u].size() - 1);
    for(auto v : adj[u]){
        if(v == dad[u]) continue;
        dad[v] = u, prep(v);
        inp[u] |= inp[v];
    }
}
void dfs(ll u){
    if(dad[u] == t && !inp[u]) return;
    for(auto v : adj[u]){
        if(v == dad[u]) continue;
        limb[v] = limb[u] + deg[u] - (inp[u] && u != m);
        dfs(v);
        if(!inp[v]) DpV[u].push_back(-dp[v]);
    }
    sort(DpV[u].begin(), DpV[u].end());
    if(deg[u] >= 2) dp[u] = -DpV[u][1];
    else dp[u] = limb[u] + (deg[u] > 0);
}
bool check(ll k){
    ll u = m, c = 1; //streak
    while(u != t){
        ll my = lower_bound(DpV[u].begin(), DpV[u].end(), -k) - DpV[u].begin();
        if(c < my || k < my) return 0;
        k -= my, c -= my, u = dad[u], c ++;
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> t >> m;
    if(m == t) return cout << 0, 0;
    for(int i = 1; i < n; i ++){
        ll u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }
    prep(t), dfs(t);
    ll low = -1, hig = n + 1;
    while(hig - low > 1){
        ll mid = (low + hig) / 2;
        if(check(mid)) hig = mid;
        else           low = mid;
    }
    cout << hig << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35