Submission #511011

#	Time	Username	Problem	Language	Result	Execution time	Memory
511011		Monarchuwu	Mousetrap (CEOI17_mousetrap)	C++17	100 / 100	850 ms	166732 KiB

mousetrap

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int N = 1e6 + 16;
int n, t, m;
vector<int> g[N];

bool checksubtask2() { // It is guaranteed that a passage between rooms m and t exists.
    for (int v : g[m])
        if (v == t) return true;
    return false;
}
namespace subtask2 {
    int dfs(int u, int p) {
        if (g[u].size() == 1) return 0; // hết đường
        if (g[u].size() == 2) return 1; // còn 1 đường nhưng sẽ bị chặn
        vector<int> res;
        for (int v : g[u]) if (v != p) {
            res.push_back(dfs(v, u) + 1); // nếu chuột chạy vào v thì min bước là ? (+1 lượt dọn phân khi quay lại)
        }
        sort(all(res), greater<int>());
        return g[u].size() - 2 + res[1]; // chặn đường thứ nhất, chuột đi vào đường thứ nhì
    }
    void solve() {
        cout << dfs(m, t) << '\n';
    }
}

namespace subtask4 {
    // par   : để đi từ m->t
    // child : để đi từ t->m
    int par[N], child[N];
    bool dfs_find(int u) { // có phải subtree chứa m ?
        for (int v : g[u]) if (v != par[u]) {
            par[v] = u;
            if (dfs_find(v)) child[u] = v;
        }
        return child[u] || u == m;
    }

    int dfs_dp(int u, int p) {
        if (g[u].size() == 1) return 0; // hết đường
        if (g[u].size() == 2) return 1; // còn 1 đường nhưng sẽ bị chặn
        vector<int> res;
        for (int v : g[u]) if (v != p) {
            res.push_back(dfs_dp(v, u) + 1); // nếu chuột chạy vào v thì min bước là ? (+1 lượt dọn phân khi quay lại)
        }
        sort(all(res), greater<int>());
        return g[u].size() - 2 + res[1]; // chặn đường thứ nhất, chuột đi vào đường thứ nhì
    }
    vector<int> dp[N], path;
    void getPath() {
        int u = child[t], cnt(0), cnttmp(0);
        while (u) {
            cnttmp = cnt + max(0, (int)g[u].size() - 2 - (child[u] != 0)); //chặn nhưng chừa 1 đường chui vào
            path.push_back(u);

            for (int v : g[u]) if (v != par[u] && v != child[u]) {
                dp[u].push_back(dfs_dp(v, u) + 1 + cnttmp);
            }
            sort(all(dp[u]), greater<int>());

            cnt += max(0, (int)g[u].size() - 1 - (child[u] != 0)); // chặn hết
            u = child[u];
        }

        //path.push_back(m);
        //dp[m].push_back(dfs_dp(m, par[m]) + cnt);
    }

    bool check(int k) { // bắt được chuột trong k lượt?
        int cnt(0), used;
        for (int u : path) {
            ++cnt; // tăng 1 lượt đặt chặn

            priority_queue<int> q;
            for (int v : dp[u]) {
                q.push(v);
            }

            used = 0;
            while (!q.empty() && q.top() - used > k) {
                q.pop();
                if (cnt == 0 || k == 0) return false; // không thể chặn
                --cnt, --k; // chặn và tốn 1 lượt
                ++used;
            }
        }
        return true;
    }
    void solve() {
        dfs_find(t);
        getPath();
        reverse(all(path)); // m->child[t]

        int lo(0), hi(n * 2), mid;
        while (lo <= hi) {
            mid = (lo + hi) >> 1;
            if (check(mid))
                hi = mid - 1;
            else lo = mid + 1;
        }
        cout << hi + 1 << '\n';
    }
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> t >> m;
    for (int i = 1, u, v; i < n; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (checksubtask2())
        subtask2::solve();
    else subtask4::solve();
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
// 5 1 4 1 2 2 3 3 4 4 5
// 4 1 4 1 2 2 3 3 4 4 5

• Subtask 1: 20 / 20
• Subtask 2: 25 / 25
• Subtask 3: 20 / 20
• Subtask 4: 35 / 35