Submission #634087

#	Time	Username	Problem	Language	Result	Execution time	Memory
634087		rainliofficial	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	908 ms	178124 KiB

mousetrap

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
#define sz(x) (int)x.size()

/* 
Date: 2022/08/22 17:18
Problem Link: link
Topic(s):
Time Spent:
Solution Notes:
Root the tree at node t, where the mouse should end up.
For every subtree on the path from t to m, calculate the amount of time it takes for Dumbo to get the mouse down and
up the subtree. Meaning we would have to clean edges eventually to get the mouse back up the subtree. 
We can do this using a dp: dp[u] = second max of dp[v] + # of children, where v is a children of u. 

Now, we have to determine the order that we want to block these subtrees. We have to consider both the level these subtrees
are on and their dp value. We can imagine this as the "urgency" of a subtree. A subtree is more urgent if it is closer to the
mouse (or just that the mouse can reach it if you don't block it) and has higher dp value.

For example, if the mouse if on a node of depth 3, and it has 2 children of dp value == 2. The next level above has a node
without any children. Two levels above is a node with three children, of dp values 5, 6, 7 for example. Here, the most
urgent node is the one with dp value == 7, then 6, 5, and then 2. Meaning although the dp value 2 subtrees are closer to the
mouse right now, we want to the subtrees higher up with larger dp values first. If for any step we don't block off a subtree
on the node that's two levels up (the one with subtrees 5, 6, 7), the mouse can get into one of those subtrees, which has higher
value than 2, which is beneficial for the mouse. 

However, if there were only two nodes of values 7 and 6 on that node two levels above, we are allowed to block off one of the
dp == 2 subtrees. So as you can see, there can be a lot of factors determining which subtree to block.

Essientially, the problems becomes how do we minimize the max dp value of the subtree that the mouse can go to. 
When hearing this "minimize the max", we should think about binary search. 

Let's binary search on the max dp value that we would allow the mouse to enter, i.e. we block every subtree with higher
value. Then, if the mouse is able to get into such a subtree, then we increase the max value, otherwise decrease it. 
*/

const int MAXN = 1e6+5, INF = 1e9;
int n, t, m, par[MAXN], dep[MAXN], dp[MAXN], deg[MAXN];
vector<int> arr[MAXN];
bool onPath[MAXN];

void dfs(int at, int p, int d = 0){
    par[at] = p;
    dep[at] = d;
    for (int u : arr[at]){
        if (u != p){
            dfs(u, at, d+1);
        }
    }
}
void dfs2(int at, int p){
    int mx = 0, mx2 = 0;
    int numChildren = 0;
    for (int u : arr[at]){
        if (u != p){
            numChildren++;
            dfs2(u, at);
            if (dp[u] >= mx){
                mx2 = mx;
                mx = dp[u];
            }else if (dp[u] > mx2){
                mx2 = dp[u];
            }
        }
    }
    dp[at] = mx2 + numChildren;
}

bool check(int x, vector<int>& path){
    int sumdeg = 0; // the branches we need 
    for (int i : path){
        sumdeg += deg[i];
    }
    if (sumdeg > x){
        return false;
    }
    int cur = 0, need = 0;
    for (int i : path){
        cur++;
        int reach = 0;
        for (int u : arr[i]){
            if (onPath[u]){
                continue;
            }
            reach += (dp[u] + sumdeg) <= x;
            need += (dp[u] + sumdeg) > x;
        }
        sumdeg -= reach; // if the mouse enters any of these subtrees, I know I can win within x moves, so I don't care about cutting them off early 
        if (need > cur){
            return false;
        }
    }
    return true;
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    cin >> n >> t >> m;
    t--; m--;
    for (int i=0; i<n-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    dfs(t, -1);
    vector<int> path;
    int cur = m;
    while (cur != t){
        path.push_back(cur);
        onPath[cur] = true;
        cur = par[cur];
    }
    onPath[t] = true;
    for (int i=0; i<n; i++){
        for (int u : arr[i]){
            if (u != par[i] && !onPath[u]){
                deg[i]++;
            }
        }
    }
    for (int i=0; i<sz(path); i++){
        for (int u : arr[path[i]]){
            if (!onPath[u]){
                dfs2(u, path[i]);
            }
        }
    }
    int low = 0, high = INF;
    while (low < high){
        int mid = (low + high)/2;
        if (check(mid, path)){
            high = mid;
        }else{
            low = mid+1;
        }
    }
    cout << low << "\n";
}

/**
 * Debugging checklist:
 * - Reset everything after each TC
 * - Integer overflow, index overflow
 * - Special cases?
 */

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