Hướng dẫn giải của Tìm kiếm cổ vật (đề HSG 12 Phú Thọ 2023-2024)


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Đồ thị là một cây. Tom và Anna mỗi ngày cùng chuyển sang một hang mới, đường đi của mỗi người là đường đơn và hai đường không có hang chung; khi một người không đi tiếp được thì cả hai dừng. Do đó số ngày tối đa là ~\max \min(a, b)~ với ~a, b~ là số hang hai người đi qua trên hai đường đơn rời nhau.

Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~

Trên cây, từ mỗi hang xuất phát có đúng một đường đơn tới mỗi hang khác. Thử mọi cặp điểm cuối ~(a, b)~, kiểm tra hai đường rời nhau và lấy ~\min~ số hang. Nếu chỉ nộp sub này: đúng 22/40 test.

Sub 2: Chia nhị phân đáp án — ~O(n \log n)~

Gọi ~x_0, \dots, x_d~ là đường nối hang xuất phát của Tom và Anna, ~h_i~ là độ sâu lớn nhất của nhánh treo tại ~x_i~ (tính bằng BFS nhiều nguồn từ các đỉnh trên đường). Tom đi dọc đường đến ~x_j~ rồi rẽ vào nhánh được ~j + 1 + h_j~ hang; Anna đi từ ~x_d~ về ~x_k~ rồi rẽ được ~d - k + 1 + h_k~ hang, với ~j < k~ để hai đường rời nhau. Chia nhị phân ~t~: tồn tại ~t~ khi tìm được ~j~ nhỏ nhất đạt ít nhất ~t~ cho Tom và ~k~ lớn nhất đạt ít nhất ~t~ cho Anna mà ~j < k~. Nếu chỉ nộp sub này: đúng 40/40 test.

Chương trình hoàn chỉnh

Hàm main đọc cây; ~n \le 100~ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

#include <bits/stdc++.h>
using namespace std;

int n, s0, t0;
vector<int> adj[200005];

// đường đi đơn từ s tới mọi đỉnh (cây nên mỗi đỉnh có đúng một đường): trả về cha
vector<int> bfsParent(int s, vector<int>& dist) {
    vector<int> par(n + 1, 0);
    dist.assign(n + 1, -1);
    queue<int> q; q.push(s); dist[s] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] < 0) { dist[v] = dist[u] + 1; par[v] = u; q.push(v); }
    }
    return par;
}

// Sub 1: vét cạn, dùng khi n <= 100
// Tom đi tới đỉnh a, Anna đi tới đỉnh b theo đường đơn; hai đường không giao nhau,
// số ngày = min(số hang Tom đi qua, số hang Anna đi qua)
void sub1() {
    vector<int> d1, d2;
    auto p1 = bfsParent(s0, d1), p2 = bfsParent(t0, d2);
    int best = 0;
    for (int a = 1; a <= n; a++) {
        vector<char> used(n + 1, 0);
        for (int x = a; x != 0; x = p1[x]) used[x] = 1;
        for (int b = 1; b <= n; b++) {
            bool ok = true;
            for (int x = b; x != 0; x = p2[x]) if (used[x]) { ok = false; break; }
            if (ok) best = max(best, min(d1[a] + 1, d2[b] + 1));
        }
    }
    printf("%d\n", best);
}

// Sub 2: chia nhị phân đáp án, O(n log n)
// Gọi x_0..x_d là đường từ s0 tới t0, h_i là độ sâu lớn nhất của nhánh treo ở x_i (không đi vào đường chính).
// Tom đi dọc đường tới x_j rồi rẽ vào nhánh: được j + 1 + h_j hang.
// Anna đi từ x_d ngược về x_k rồi rẽ: được (d - k) + 1 + h_k hang, với j < k.
void sub2() {
    vector<int> d1;
    auto par = bfsParent(s0, d1);
    vector<int> path;
    for (int x = t0; x != 0; x = par[x]) path.push_back(x);
    reverse(path.begin(), path.end());       // path[0] = s0, path.back() = t0
    int d = path.size() - 1;
    if (d == 0) { printf("0\n"); return; }
    // BFS nhiều nguồn từ các đỉnh trên đường chính
    vector<int> dist(n + 1, -1), owner(n + 1, 0), h(d + 1, 0), idx(n + 1, -1);
    queue<int> q;
    for (int i = 0; i <= d; i++) { dist[path[i]] = 0; owner[path[i]] = i; idx[path[i]] = i; q.push(path[i]); }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        h[owner[u]] = max(h[owner[u]], dist[u]);
        for (int v : adj[u]) if (dist[v] < 0) { dist[v] = dist[u] + 1; owner[v] = owner[u]; q.push(v); }
    }
    auto feasible = [&](int t) {
        int j = -1, k = -1;
        for (int i = 0; i <= d; i++) if (i + 1 + h[i] >= t) { j = i; break; }
        for (int i = d; i >= 0; i--) if (d - i + 1 + h[i] >= t) { k = i; break; }
        return j >= 0 && k >= 0 && j < k;
    };
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (feasible(mid)) lo = mid; else hi = mid - 1;
    }
    printf("%d\n", lo);
}

int main() {
    freopen("CAU4.INP", "r", stdin);
    freopen("CAU4.OUT", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d %d", &u, &v);
        adj[u].push_back(v); adj[v].push_back(u);
    }
    scanf("%d %d", &s0, &t0);
    if (n <= 100) sub1();
    else sub2();
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.