oj.uz

답안 #633633

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633633 2022-08-22T22:23:10 Z rainliofficial Mousetrap (CEOI17_mousetrap) C++17
45 / 100
 769 ms 81112 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];
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 12 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 23776 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23740 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23828 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 274 ms 70016 KB Output is correct
2 Correct 260 ms 74544 KB Output is correct
3 Correct 769 ms 81072 KB Output is correct
4 Correct 378 ms 52356 KB Output is correct
5 Correct 729 ms 81112 KB Output is correct
6 Correct 764 ms 81112 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 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 23776 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23740 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23828 KB Output is correct
11 Correct 11 ms 23764 KB Output is correct
12 Correct 11 ms 23756 KB Output is correct
13 Correct 12 ms 23776 KB Output is correct
14 Correct 12 ms 23828 KB Output is correct
15 Correct 13 ms 23892 KB Output is correct
16 Incorrect 12 ms 23764 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 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 23776 KB Output is correct
5 Correct 13 ms 23812 KB Output is correct
6 Correct 13 ms 23764 KB Output is correct
7 Correct 13 ms 23804 KB Output is correct
8 Correct 13 ms 23740 KB Output is correct
9 Correct 12 ms 23764 KB Output is correct
10 Correct 13 ms 23828 KB Output is correct
11 Correct 274 ms 70016 KB Output is correct
12 Correct 260 ms 74544 KB Output is correct
13 Correct 769 ms 81072 KB Output is correct
14 Correct 378 ms 52356 KB Output is correct
15 Correct 729 ms 81112 KB Output is correct
16 Correct 764 ms 81112 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23756 KB Output is correct
19 Correct 12 ms 23776 KB Output is correct
20 Correct 12 ms 23828 KB Output is correct
21 Correct 13 ms 23892 KB Output is correct
22 Incorrect 12 ms 23764 KB Output isn't correct
23 Halted 0 ms 0 KB -