제출 #1081422

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1081422		Zero_OP	Mousetrap (CEOI17_mousetrap)	C++14	100 / 100	625 ms	217664 KiB

mousetrap

#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

*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35