Submission #510937

#	Time	Username	Problem	Language	Result	Execution time	Memory
510937		Monarchuwu	Mousetrap (CEOI17_mousetrap)	C++17	25 / 100	878 ms	82596 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);
        while (u) {
            cnt += max(0, (int)g[u].size() - 2 - (child[u] != 0));
            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 + cnt);
            }
            sort(all(dp[u]), greater<int>());

            u = child[u];
        }
    }

    bool check(int k) { // bắt được chuột trong k lượt?
        priority_queue<int> q;
        int cnt(0);
        for (int u : path) {
            ++cnt; // tăng 1 lượt đặt chặn
            for (int v : dp[u]) {
                if (v < k) break;
                if (cnt == 0) return false; // không thể chặn
                --cnt, --k; // chặn và tốn 1 lượt
            }
        }
        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
**/

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