Submission #349857

#	Time	Username	Problem	Language	Result	Execution time	Memory
349857		doowey	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	1081 ms	260460 KiB

mousetrap

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e6 + 100;
vector<int> T[N];
vector<pii> lis[N];

int dp[N];
int up[N];
int pp[N];

int trap;
int mouse;

void dfs(int u, int par){
    int deg = 0;
    for(auto x : T[u]) if(x != par) deg ++ ;
    for(auto x : T[u]){
        if(x==par) continue;
        pp[x]=u;
        up[x] += up[u] + (par != -1) * (deg - 1);
        dfs(x,u);
        lis[u].push_back(mp(dp[x],x));
    }
    sort(lis[u].begin(), lis[u].end());
    int mx = 0;
    if(lis[u].size() >= 2)
        mx = lis[u][lis[u].size() - 2].fi;
    dp[u]=mx+lis[u].size();
    reverse(lis[u].begin(), lis[u].end());
}

bool can(int mid){
    int cur = mouse;
    int can = 1;
    int alr = 0;
    int pv = -1;
    int cnt;
    int need;
    while(cur != trap){
        cnt = 0;
        for(auto x : lis[cur]){
            if(x.se == pv) continue;
            cnt ++ ;
        }
        need = 0;
        for(auto x : lis[cur]){
            if(x.se == pv) continue;
            if(up[cur]+x.fi+cnt+alr > mid){
                need ++ ;
                if(can == 0){
                    return false;
                }
                can -- ;
            }
        }
        alr += need;
        pv=cur;
        cur = pp[cur];
        can++;
    }
    if(alr > mid) return false;
    return true;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    cin >> trap >> mouse;
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    dfs(trap,-1);
    int lf = 0, rf = (int)n * 2;
    int mid;
    while(lf < rf){
        mid = (lf + rf) / 2;
        if(can(mid)){
            rf=mid;
        }
        else{
            lf=mid+1;
        }
    }
    cout << lf << "\n";
    return 0;
}

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