oj.uz

Submission #634087

# Submission time Handle Problem Language Result Execution time Memory
634087 2022-08-23T19:15:10 Z rainliofficial Mousetrap (CEOI17_mousetrap) C++17
100 / 100
 908 ms 178124 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23828 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 20 ms 23764 KB Output is correct
8 Correct 12 ms 23828 KB Output is correct
9 Correct 12 ms 23796 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 68732 KB Output is correct
2 Correct 250 ms 64376 KB Output is correct
3 Correct 795 ms 71860 KB Output is correct
4 Correct 383 ms 47852 KB Output is correct
5 Correct 780 ms 71840 KB Output is correct
6 Correct 777 ms 71760 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23828 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 20 ms 23764 KB Output is correct
8 Correct 12 ms 23828 KB Output is correct
9 Correct 12 ms 23796 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 12 ms 23812 KB Output is correct
12 Correct 13 ms 23876 KB Output is correct
13 Correct 13 ms 23888 KB Output is correct
14 Correct 14 ms 23856 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 13 ms 23892 KB Output is correct
17 Correct 12 ms 23892 KB Output is correct
18 Correct 13 ms 23892 KB Output is correct
19 Correct 13 ms 23788 KB Output is correct
20 Correct 12 ms 23764 KB Output is correct
21 Correct 14 ms 23764 KB Output is correct
22 Correct 13 ms 23768 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 14 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 12 ms 23828 KB Output is correct
5 Correct 13 ms 23764 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 20 ms 23764 KB Output is correct
8 Correct 12 ms 23828 KB Output is correct
9 Correct 12 ms 23796 KB Output is correct
10 Correct 12 ms 23764 KB Output is correct
11 Correct 293 ms 68732 KB Output is correct
12 Correct 250 ms 64376 KB Output is correct
13 Correct 795 ms 71860 KB Output is correct
14 Correct 383 ms 47852 KB Output is correct
15 Correct 780 ms 71840 KB Output is correct
16 Correct 777 ms 71760 KB Output is correct
17 Correct 12 ms 23812 KB Output is correct
18 Correct 13 ms 23876 KB Output is correct
19 Correct 13 ms 23888 KB Output is correct
20 Correct 14 ms 23856 KB Output is correct
21 Correct 12 ms 23892 KB Output is correct
22 Correct 13 ms 23892 KB Output is correct
23 Correct 12 ms 23892 KB Output is correct
24 Correct 13 ms 23892 KB Output is correct
25 Correct 13 ms 23788 KB Output is correct
26 Correct 12 ms 23764 KB Output is correct
27 Correct 14 ms 23764 KB Output is correct
28 Correct 13 ms 23768 KB Output is correct
29 Correct 14 ms 23832 KB Output is correct
30 Correct 287 ms 82100 KB Output is correct
31 Correct 341 ms 82180 KB Output is correct
32 Correct 408 ms 107464 KB Output is correct
33 Correct 333 ms 178124 KB Output is correct
34 Correct 780 ms 85084 KB Output is correct
35 Correct 829 ms 85056 KB Output is correct
36 Correct 908 ms 87904 KB Output is correct
37 Correct 872 ms 87836 KB Output is correct
38 Correct 604 ms 87532 KB Output is correct
39 Correct 617 ms 87496 KB Output is correct
40 Correct 650 ms 87476 KB Output is correct