oj.uz

Submission #1081422

# Submission time Handle Problem Language Result Execution time Memory
1081422 2024-08-30T04:34:52 Z Zero_OP Mousetrap (CEOI17_mousetrap) C++14
100 / 100
 625 ms 217664 KB 
#include<bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(v) "[" #v " = " << (v) << "]"
#define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define rep(i, l, r) for(int i = (l); i < (r); ++i)

using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using ld = long double;

template<typename T> 
    bool minimize(T& a, const T& b){
        if(a > b){
            return a = b, true;
        }  return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){    
        if(a < b){
            return a = b, true;
        } return false;
    }

template<int dimension, typename T>
struct tensor : public vector<tensor<dimension - 1, T>> {
    static_assert(dimension > 0, "Dimension must be positive !\n");
    template<typename... Args>
    tensor(int n = 0, Args... args) : vector<tensor<dimension - 1, T>> (n, tensor<dimension - 1, T>(args...)) {}
};
 
template<typename T>
struct tensor<1, T> : public vector<T> {
    tensor(int n = 0, T val = T()) : vector<T>(n, val) {}
};

const int MAX = 1e6 + 5;

int n, t, m, par[MAX], dp[MAX], moves_above[MAX];
vector<int> adj[MAX], L[MAX];

/*
let dp[u] = minimum moves to make the mouse go up to par[u]
the main strategy is let the mouse stuck at the most optimal leaf, then we blocks all the "bad" 
edges which connect the vertex on the path (mouse to the leaf) 
to other subtrees before clean the ways from that leaf to the root T

*/

void dfs(int u, int p = -1){
    if(p != -1) moves_above[u] = moves_above[p] + sz(adj[p]) - 2 + (u == m);
    vector<int> nCosts;
    for(int v : adj[u]) if(v != p){
        par[v] = u;
        dfs(v, u);
        nCosts.push_back(dp[v]);
    }

    if(sz(nCosts) <= 1) dp[u] = sz(nCosts);
    else{
        sort(all(nCosts), greater<int>());
        dp[u] = sz(nCosts) + nCosts[1];
    }
}

void testcase(){
    cin >> n >> t >> m;
    rep(i, 1, n){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }

    dfs(t);

    
    
    int u = m, last = -1, dist = 0;
    vector<int> chain;
    while(u != t){
        chain.push_back(u);
        for(int v : adj[u]){
            if(v != par[u] && v != last){
                L[u].push_back(dp[v] + moves_above[v] + 1);
            }
        }

        sort(all(L[u]));

        last = u;
        u = par[u];
    }

    auto f = [&](int x) -> bool{
        int freeBlocks = 0;
        for(int u : chain){
            ++freeBlocks;
            for(int val : L[u]){
                int delta = 0;
                if(val > x){
                    --freeBlocks;
                    if(freeBlocks < 0) return false;
                    ++delta;
                }

                x -= delta;
                if(x < 0) return false;
            }
        }    

        return true;
    };

    int l = 0, r = 2 * n, ans = r;
    while(l <= r){
        int mid = l + r >> 1;
        if(f(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    file("task");

    int T = 1;
    // cin >> T;
    while(T--){
        testcase();
    }

    return 0;
}

/*

Testcase 1 : 
10 1 4
1 2
2 3
2 4
3 9
3 5
4 7
4 6
6 8
7 10

Testcase 2 : 
12 1 2
1 2
2 3
3 4
4 5
4 6
3 7
7 8
8 10
7 9
2 11
11 12

*/

Compilation message

mousetrap.cpp: In function 'void testcase()':
mousetrap.cpp:122:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  122 |         int mid = l + r >> 1;
      |                   ~~^~~
mousetrap.cpp:84:27: warning: unused variable 'dist' [-Wunused-variable]
   84 |     int u = m, last = -1, dist = 0;
      |                           ^~~~
mousetrap.cpp: In function 'int main()':
mousetrap.cpp:9:55: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:133:5: note: in expansion of macro 'file'
  133 |     file("task");
      |     ^~~~
mousetrap.cpp:9:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | #define file(name) if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mousetrap.cpp:133:5: note: in expansion of macro 'file'
  133 |     file("task");
      |     ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 28 ms 47192 KB Output is correct
4 Correct 21 ms 47196 KB Output is correct
5 Correct 21 ms 47448 KB Output is correct
6 Correct 22 ms 47448 KB Output is correct
7 Correct 21 ms 47192 KB Output is correct
8 Correct 22 ms 47452 KB Output is correct
9 Correct 21 ms 47448 KB Output is correct
10 Correct 20 ms 47196 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 103764 KB Output is correct
2 Correct 236 ms 98080 KB Output is correct
3 Correct 582 ms 104528 KB Output is correct
4 Correct 199 ms 75860 KB Output is correct
5 Correct 564 ms 104528 KB Output is correct
6 Correct 572 ms 104528 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 28 ms 47192 KB Output is correct
4 Correct 21 ms 47196 KB Output is correct
5 Correct 21 ms 47448 KB Output is correct
6 Correct 22 ms 47448 KB Output is correct
7 Correct 21 ms 47192 KB Output is correct
8 Correct 22 ms 47452 KB Output is correct
9 Correct 21 ms 47448 KB Output is correct
10 Correct 20 ms 47196 KB Output is correct
11 Correct 20 ms 47448 KB Output is correct
12 Correct 23 ms 47452 KB Output is correct
13 Correct 21 ms 47452 KB Output is correct
14 Correct 22 ms 47448 KB Output is correct
15 Correct 21 ms 47480 KB Output is correct
16 Correct 21 ms 47448 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 21 ms 47452 KB Output is correct
19 Correct 21 ms 47304 KB Output is correct
20 Correct 20 ms 47516 KB Output is correct
21 Correct 19 ms 47272 KB Output is correct
22 Correct 21 ms 47444 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 47196 KB Output is correct
2 Correct 21 ms 47196 KB Output is correct
3 Correct 28 ms 47192 KB Output is correct
4 Correct 21 ms 47196 KB Output is correct
5 Correct 21 ms 47448 KB Output is correct
6 Correct 22 ms 47448 KB Output is correct
7 Correct 21 ms 47192 KB Output is correct
8 Correct 22 ms 47452 KB Output is correct
9 Correct 21 ms 47448 KB Output is correct
10 Correct 20 ms 47196 KB Output is correct
11 Correct 223 ms 103764 KB Output is correct
12 Correct 236 ms 98080 KB Output is correct
13 Correct 582 ms 104528 KB Output is correct
14 Correct 199 ms 75860 KB Output is correct
15 Correct 564 ms 104528 KB Output is correct
16 Correct 572 ms 104528 KB Output is correct
17 Correct 20 ms 47448 KB Output is correct
18 Correct 23 ms 47452 KB Output is correct
19 Correct 21 ms 47452 KB Output is correct
20 Correct 22 ms 47448 KB Output is correct
21 Correct 21 ms 47480 KB Output is correct
22 Correct 21 ms 47448 KB Output is correct
23 Correct 20 ms 47448 KB Output is correct
24 Correct 21 ms 47452 KB Output is correct
25 Correct 21 ms 47304 KB Output is correct
26 Correct 20 ms 47516 KB Output is correct
27 Correct 19 ms 47272 KB Output is correct
28 Correct 21 ms 47444 KB Output is correct
29 Correct 21 ms 47452 KB Output is correct
30 Correct 222 ms 103684 KB Output is correct
31 Correct 219 ms 103764 KB Output is correct
32 Correct 323 ms 217664 KB Output is correct
33 Correct 271 ms 213408 KB Output is correct
34 Correct 625 ms 104528 KB Output is correct
35 Correct 549 ms 104944 KB Output is correct
36 Correct 594 ms 118760 KB Output is correct
37 Correct 604 ms 118860 KB Output is correct
38 Correct 454 ms 120776 KB Output is correct
39 Correct 447 ms 120776 KB Output is correct
40 Correct 427 ms 120776 KB Output is correct