Submission #939560

#	Time	Username	Problem	Language	Result	Execution time	Memory
939560		phoenix0423	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	729 ms	162648 KiB

mousetrap

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
const int maxn = 1e6 + 5;
const int INF = 1e18;
vector<int> adj[maxn];
int dp[maxn], par[maxn];
int n, t, m;

void dfs(int pos, int prev){
    if(prev != -1) adj[pos].erase(find(adj[pos].begin(), adj[pos].end(), prev));
    int mx = 0, sc = 0;
    for(auto x : adj[pos]){
        par[x] = pos;
        dfs(x, pos);    
        if(dp[x] >= mx) sc = mx, mx = dp[x];
        else sc = max(sc, dp[x]);
    }
    dp[pos] = sc + adj[pos].size();
}

signed main(void){
    fastio;
    cin>>n>>t>>m;
    t--, m--;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(t, -1);
    int ttld = 0;
    int l = -1, r = n;
    while(l + 1 < r){
        int mid = (l + r) / 2; // cost to lead mouse into a dead end
        int ok = 1;
        int dif = 0, prev = -1;
        int canuse = 0;
        int cur = m;
        int used = 0;
        while(cur != t){
            canuse++;
            int tmp = 0;
            for(auto x : adj[cur]){
                if(x == prev) continue;
                if(dp[x] - dif + used > mid){
                    if(!canuse) ok = 0;
                    else canuse--, tmp++;
                }
            }
            used += tmp;
            dif += adj[cur].size() - (prev != -1);
            prev = cur;
            cur = par[cur];
        }
        ttld = dif;
        if(ok) r = mid;
        else l = mid;
    }
    cout<<r + ttld<<"\n";
}
/*

24 1 12
1 4
4 5
5 6
6 7
5 8
8 9
8 10
10 11
10 12
10 13
8 14
14 15
15 18
15 16
15 17
14 19
19 20
19 21
11 2
13 3
9 22
9 23
9 24
*/

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