oj.uz

답안 #633632

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633632 2022-08-22T22:22:13 Z rainliofficial Mousetrap (CEOI17_mousetrap) C++17
20 / 100
 220 ms 89868 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 = 5e5+5, INF = 1e9;
int n, t, m, par[MAXN], dep[MAXN], dp[MAXN];
vector<int> arr[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<pii>& dps){
    if (sz(dps) == 0){
        return true;
    }
    vector<int> deps;
    for (int i=0; i<sz(dps); i++){
        if (dps[i].first >= x){
            deps.push_back(dps[i].second);
        }
    }
    sort(deps.begin(), deps.end(), greater<int>());
    int cur = dep[m];
    for (int i=0; i<sz(deps); i++){
        if (cur >= deps[i]){
            cur--;
        }else{
            return false;
        }
    }
    return true; // Dumbo successfully prevented the mouse from getting into a room of sz x or larger
}
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);
        cur = par[cur];
    }
    reverse(path.begin(), path.end());
    path.push_back(-1); // padding
    vector<pii> dps; 
    for (int i=0; i<sz(path)-1; i++){
        for (int u : arr[path[i]]){
            if (u != par[path[i]] && u != path[i+1]){
                dfs2(u, path[i]);
                dps.push_back({dp[u]+1, dep[path[i]]});
            }
        }
    }
    // for (auto x : dps){
    //     cout << x.first << " " << x.second << "\n";
    // }
    sort(dps.begin(), dps.end(), greater<pii>());
    // binary search on x, and check(x) returns if the mouse can enter a room with value >= x
    int low = 0, high = 2*n;
    while (low < high){
        int mid = (low + high + 1)/2;
        if (check(mid, dps)){
            high = mid - 1;
        }else{
            low = mid;
        }
    }
    if (low == 0){
        cout << sz(dps) << "\n"; // block off all
    }else{
        cout << low + sz(dps) - 1 << "\n";
    }
}

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

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12080 KB Output is correct
3 Correct 8 ms 11972 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 12016 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 220 ms 89868 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12080 KB Output is correct
3 Correct 8 ms 11972 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 12016 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 7 ms 12136 KB Output is correct
12 Correct 7 ms 12084 KB Output is correct
13 Correct 7 ms 12116 KB Output is correct
14 Correct 9 ms 12084 KB Output is correct
15 Correct 7 ms 12108 KB Output is correct
16 Incorrect 6 ms 12116 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 12080 KB Output is correct
3 Correct 8 ms 11972 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 11988 KB Output is correct
6 Correct 7 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 6 ms 12016 KB Output is correct
9 Correct 7 ms 11988 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Runtime error 220 ms 89868 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -