Đào kênh (Đề tự luyện HSG Tin quốc gia – Bài 2)

Nguồn: Đề tự luyện HSG Tin học quốc gia – Bài 2 (đề tự soạn)Độ khó: KhóĐồ thịCầu (Tarjan)Thành phần 2-liên thông cạnhCâyQHĐ đổi gốc

Đề bài

Đào kênh

Có $N$ bến ghe và $M$ con kênh hai chiều (giữa hai bến có thể có nhiều kênh), mạng kênh liên thông. Một kênh là xung yếu nếu chỉ riêng nó bị bồi lấp thì có hai bến không còn đi được tới nhau. Xã sẽ đào thêm đúng một kênh mới nối bến $u$ với một bến $v \ne u$ (được phép trùng chỗ đã có kênh). Với mỗi bến $u$, hãy tính $a_u$ – số kênh xung yếu ít nhất có thể còn lại nếu kênh mới đào từ $u$, và $b_u$ – số bến $v$ đạt được con số đó.

Dữ liệu vào: dòng đầu $N, M$ $(2 \le N \le 2\cdot 10^5;\ N - 1 \le M \le 3\cdot 10^5)$; $M$ dòng sau mỗi dòng $x_i, y_i$ $(x_i \ne y_i)$.

Kết quả: $N$ dòng, dòng thứ $u$ gồm $a_u$ và $b_u$.

Subtask 1 (15%): $N \le 300$, $M \le 600$.
Subtask 2 (25%): $N \le 5000$, $M \le 10^4$.
Subtask 3 (25%): $M = N - 1$.
Subtask 4 (35%): không có ràng buộc gì thêm.

Giới hạn thời gian: C++ 1 giây, Python/PyPy 5 giây.

Input

Output

Giải thích

Có 5 kênh xung yếu: $3-4$, $4-5$, $2-6$, $8-9$, $7-10$. Từ bến 1, đào tới bến 5, 9 hoặc 10 thì còn 3 kênh xung yếu. Từ bến 5, đào tới bến 9 hoặc 10 thì chỉ còn 1.

Input

Output

Giải thích

Cả 4 kênh đều xung yếu. Từ bến 1, đào kênh $1-4$ thì còn kênh $3-5$, đào kênh $1-5$ thì còn kênh $3-4$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Đào kênh

Lời mở đầu

"Kênh xung yếu" chính là cầu (bridge) của đồ thị vô hướng. Bài toán gồm hai tầng: tìm cầu, rồi trả lời câu hỏi cho từng bến. Ba nhận xét then chốt:

Đào kênh $u-v$ thì cầu nào biến mất? Kênh mới không bao giờ là cầu (bỏ nó đi thì mạng cũ vẫn liên thông). Một cầu $e$ cũ hết xung yếu khi và chỉ khi nó ngăn cách $u$ với $v$ (mọi đường $u \to v$ đều đi qua $e$): lấp $e$ thì ghe vẫn vòng qua kênh mới. Nếu $u, v$ nằm cùng một phía của $e$ thì lấp $e$ vẫn chia mạng làm hai như cũ. Các kênh không xung yếu thì vẫn không xung yếu.
Gom cụm. Gọi hai bến là cùng cụm nếu đi được tới nhau mà không qua kênh xung yếu nào (đây là các thành phần 2-liên thông cạnh). Co mỗi cụm thành một đỉnh, các kênh xung yếu thành cạnh, ta được một cây – gọi là "cây cụm". Các cầu ngăn cách $u$ với $v$ đúng là các cạnh trên đường đi giữa cụm$(u)$ và cụm$(v)$ trong cây.
Đếm. Gọi $B$ là số cầu. Đào kênh $u - v$ còn lại $B - \text{dist}(\text{cụm}(u), \text{cụm}(v))$ cầu. Vậy $a_u = B - e(\text{cụm}(u))$ với $e(c)$ là khoảng cách xa nhất từ $c$ tới một cụm khác trong cây, và $b_u$ là tổng số bến của các cụm ở khoảng cách đó (không phải số cụm!). Trường hợp không có cầu ($B = 0$): $a_u = 0$, $b_u = N - 1$.

Ví dụ 1: hai cụm có chu trình được tô màu; co lại ta được cây cụm 6 đỉnh, 5 cạnh.

Lộ trình:

Cách 1Thử mọi kênh mới · 15%Cách 2Tarjan + BFS trên cây cụm · 40%Cách 3Đồ thị là cây: QHĐ đổi gốc · 65%Cách 4Ghép tất cả · 100%

Cách 1Thử mọi kênh mới – O(N² (N + M)) · 15%

Làm đúng như đề: với mỗi cặp $(u, v)$, thêm kênh $u - v$ vào đồ thị, đếm số cầu, rồi bỏ kênh đó ra. Đếm cầu bằng thuật toán Tarjan: duyệt DFS, gán $tin[v]$ là thời điểm thăm $v$ và $low[v]$ là $tin$ nhỏ nhất mà cây con của $v$ "với tới" được bằng một kênh ngược. Kênh cây $v \to to$ là cầu khi và chỉ khi $low[to] > tin[v]$: cây con của $to$ không có đường nào khác quay lên $v$ hoặc cao hơn.

Bẫy kênh song song

Khi duyệt các kênh kề $v$, phải bỏ qua đúng con kênh vừa đi xuống $v$ (so sánh số hiệu kênh), chứ không được bỏ qua mọi kênh nối tới đỉnh cha. Nếu giữa $p$ và $v$ có hai kênh song song thì kênh thứ hai là đường quay về – hai kênh đó đều không xung yếu. Code "bỏ qua đỉnh cha" (wrong_parent.cpp) sai ở hầu hết các test có kênh song song.

#include <bits/stdc++.h>
using namespace std;
int n, m, timer_;
vector<vector<pair<int, int>>> g;
vector<int> tin, low;
int bridges;
void dfs(int v, int pe) {                      // Tarjan: pe = so hieu kenh vua di toi v
    tin[v] = low[v] = ++timer_;
    for (auto [to, id] : g[v]) {
        if (id == pe) continue;
        if (tin[to]) low[v] = min(low[v], tin[to]);
        else {
            dfs(to, id);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v]) bridges++;
        }
    }
}
int countBridges() {
    tin.assign(n + 1, 0); low.assign(n + 1, 0);
    timer_ = 0; bridges = 0;
    dfs(1, -1);
    return bridges;
}
int main() {
    scanf("%d %d", &n, &m);
    g.assign(n + 1, {});
    for (int i = 0; i < m; i++) {
        int u, v; scanf("%d %d", &u, &v);
        g[u].push_back({v, i}); g[v].push_back({u, i});
    }
    for (int u = 1; u <= n; u++) {
        int best = INT_MAX, cnt = 0;
        for (int v = 1; v <= n; v++) if (v != u) {
            g[u].push_back({v, m}); g[v].push_back({u, m});      // dao thu kenh moi (u, v)
            int b = countBridges();
            g[u].pop_back(); g[v].pop_back();
            if (b < best) { best = b; cnt = 1; }
            else if (b == best) cnt++;
        }
        printf("%d %d\n", best, cnt);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    g = [[] for _ in range(n + 1)]
    for i in range(m):
        u = int(data[2 + 2 * i]); v = int(data[3 + 2 * i])
        g[u].append((v, i)); g[v].append((u, i))

    def count_bridges():
        # Tarjan khu de quy: pe[v] = so hieu kenh vua di toi v
        tin = [0] * (n + 1); low = [0] * (n + 1); pe = [-1] * (n + 1); it = [0] * (n + 1)
        timer = 1; tin[1] = low[1] = 1
        st = [1]; cnt = 0
        while st:
            v = st[-1]
            if it[v] < len(g[v]):
                to, eid = g[v][it[v]]; it[v] += 1
                if eid == pe[v]:
                    continue
                if tin[to]:
                    low[v] = min(low[v], tin[to])
                else:
                    timer += 1; tin[to] = low[to] = timer; pe[to] = eid
                    st.append(to)
            else:
                st.pop()
                if st:
                    p = st[-1]
                    low[p] = min(low[p], low[v])
                    if low[v] > tin[p]:
                        cnt += 1
        return cnt

    out = []
    for u in range(1, n + 1):
        best = None; cnt = 0
        for v in range(1, n + 1):
            if v == u:
                continue
            g[u].append((v, m)); g[v].append((u, m))      # dao thu kenh moi (u, v)
            b = count_bridges()
            g[u].pop(); g[v].pop()
            if best is None or b < best:
                best = b; cnt = 1
            elif b == best:
                cnt += 1
        out.append("%d %d" % (best, cnt))
    sys.stdout.write("\n".join(out) + "\n")

main()

Không gian$O(N + M)$

Thời gian$O(N^2 (N + M))$

Bản C++ dùng đệ quy cho gọn – đủ cho $N \le 300$. Với $N$ lớn, đệ quy sâu $2\cdot 10^5$ tầng dễ tràn ngăn xếp, nên từ Cách 2 ta viết Tarjan khử đệ quy bằng một ngăn xếp tự quản lý và con trỏ it[v] (kênh kế tiếp cần xét của $v$).

Cách 2Tarjan một lần + BFS trên cây cụm – O(N + M + K²) · 40%

Theo ba nhận xét ở trên:

Chạy Tarjan một lần để đánh dấu các cầu.
Gom cụm: loang (DFS/BFS) từ mỗi bến chưa có cụm, chỉ đi qua các kênh không xung yếu. Ghi lại số bến $sz$ của mỗi cụm. Có $K$ cụm thì có $B = K - 1$ cầu.
Dựng cây cụm và BFS từ từng cụm $c$ để tìm khoảng cách xa nhất $e(c)$ và tổng $sz$ của các cụm ở khoảng cách đó.

Mô phỏng dưới đây chạy Tarjan khử đệ quy (giống hệt code) rồi tô màu các cụm. Cạnh xanh là kênh cây DFS, cạnh xám nét đứt là kênh ngược, cạnh đỏ là kênh xung yếu:

N Các kênh x y

Ví dụ nhanh:

Tarjan và gom cụm chạy trong $O(N + M)$; phần BFS từ $K$ cụm tốn $O(K^2)$, đủ cho $N \le 5000$.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> eu(m), ev(m);
    vector<vector<pair<int, int>>> g(n + 1);           // (ben ke, so hieu kenh)
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &eu[i], &ev[i]);
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    // 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    vector<int> tin(n + 1, 0), low(n + 1), pe(n + 1, -1), it(n + 1, 0);
    vector<char> br(m, 0);
    int timer = 0;
    vector<int> st = {1};
    tin[1] = low[1] = ++timer;
    while (!st.empty()) {
        int v = st.back();
        if (it[v] < (int)g[v].size()) {
            auto [to, id] = g[v][it[v]++];
            if (id == pe[v]) continue;
            if (tin[to]) low[v] = min(low[v], tin[to]);
            else { tin[to] = low[to] = ++timer; pe[to] = id; st.push_back(to); }
        } else {
            st.pop_back();
            if (pe[v] >= 0) {
                int p = eu[pe[v]] ^ ev[pe[v]] ^ v;
                low[p] = min(low[p], low[v]);
                if (low[v] > tin[p]) br[pe[v]] = 1;     // kenh pe[v] la kenh xung yeu
            }
        }
    }
    // 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    vector<int> comp(n + 1, -1);
    vector<long long> sz;
    int K = 0;
    for (int s = 1; s <= n; s++) if (comp[s] < 0) {
        comp[s] = K; sz.push_back(0);
        vector<int> q = {s};
        while (!q.empty()) {
            int v = q.back(); q.pop_back(); sz[K]++;
            for (auto [to, id] : g[v]) if (!br[id] && comp[to] < 0) { comp[to] = K; q.push_back(to); }
        }
        K++;
    }
    if (K == 1) {                                       // khong co kenh xung yeu nao
        for (int u = 1; u <= n; u++) printf("0 %d\n", n - 1);
        return 0;
    }
    // 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    vector<vector<int>> t(K);
    for (int i = 0; i < m; i++) if (br[i]) {
        t[comp[eu[i]]].push_back(comp[ev[i]]);
        t[comp[ev[i]]].push_back(comp[eu[i]]);
    }
    int B = K - 1;
    // 4) BFS tu tung cum: tim cum xa nhat va tong so ben cua cac cum xa nhat
    vector<int> fd(K);
    vector<long long> fk(K);
    vector<int> d(K);
    for (int c = 0; c < K; c++) {
        fill(d.begin(), d.end(), -1);
        d[c] = 0;
        vector<int> q = {c};
        for (int i = 0; i < (int)q.size(); i++)
            for (int y : t[q[i]]) if (d[y] < 0) { d[y] = d[q[i]] + 1; q.push_back(y); }
        int mx = 0; long long cnt = 0;
        for (int y = 0; y < K; y++) {
            if (d[y] > mx) { mx = d[y]; cnt = sz[y]; }
            else if (d[y] == mx) cnt += sz[y];
        }
        fd[c] = mx; fk[c] = cnt;
    }
    for (int u = 1; u <= n; u++) {
        int c = comp[u];
        printf("%d %lld\n", B - fd[c], fk[c]);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    eu = [0] * m; ev = [0] * m
    deg = [0] * (n + 2)
    for i in range(m):
        a = int(data[2 + 2 * i]); b = int(data[3 + 2 * i])
        eu[i] = a; ev[i] = b
        deg[a] += 1; deg[b] += 1
    # danh sach ke dang mang phang: ke cua v nam o adj[start[v] : start[v + 1]]
    start = [0] * (n + 2)
    for v in range(1, n + 1):
        start[v + 1] = start[v] + deg[v]
    pos = start[:]
    adj = [0] * (2 * m); aid = [0] * (2 * m)
    for i in range(m):
        a = eu[i]; b = ev[i]
        adj[pos[a]] = b; aid[pos[a]] = i; pos[a] += 1
        adj[pos[b]] = a; aid[pos[b]] = i; pos[b] += 1
    # 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    tin = [0] * (n + 1); low = [0] * (n + 1); pe = [-1] * (n + 1)
    it = start[:]
    br = [0] * m
    timer = 1
    tin[1] = low[1] = 1
    st = [1]
    while st:
        v = st[-1]
        k = it[v]
        if k < start[v + 1]:
            it[v] = k + 1
            to = adj[k]; eid = aid[k]
            if eid == pe[v]:
                continue
            if tin[to]:
                if tin[to] < low[v]:
                    low[v] = tin[to]
            else:
                timer += 1
                tin[to] = low[to] = timer
                pe[to] = eid
                st.append(to)
        else:
            st.pop()
            e = pe[v]
            if e >= 0:
                p = eu[e] ^ ev[e] ^ v
                if low[v] < low[p]:
                    low[p] = low[v]
                if low[v] > tin[p]:
                    br[e] = 1                  # kenh e la kenh xung yeu
    # 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    comp = [-1] * (n + 1)
    sz = []
    K = 0
    for s in range(1, n + 1):
        if comp[s] >= 0:
            continue
        comp[s] = K
        q = [s]; cnt = 0
        while q:
            v = q.pop(); cnt += 1
            for k in range(start[v], start[v + 1]):
                to = adj[k]
                if comp[to] < 0 and not br[aid[k]]:
                    comp[to] = K
                    q.append(to)
        sz.append(cnt)
        K += 1
    if K == 1:                                 # khong co kenh xung yeu nao
        sys.stdout.write(("0 %d\n" % (n - 1)) * n)
        return
    # 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    t = [[] for _ in range(K)]
    for i in range(m):
        if br[i]:
            a = comp[eu[i]]; b = comp[ev[i]]
            t[a].append(b); t[b].append(a)
    B = K - 1
    # 4) BFS tu tung cum: tim cum xa nhat va tong so ben cua cac cum xa nhat
    ansd = [0] * K; ansk = [0] * K
    for c in range(K):
        d = [-1] * K
        d[c] = 0
        q = [c]
        for x in q:
            dx = d[x] + 1
            for y in t[x]:
                if d[y] < 0:
                    d[y] = dx
                    q.append(y)
        mx = d[q[-1]]                          # BFS: dinh cuoi cung co khoang cach lon nhat
        cnt = 0
        for y in q:
            if d[y] == mx:
                cnt += sz[y]
        ansd[c] = B - mx; ansk[c] = cnt
    out = []
    for u in range(1, n + 1):
        c = comp[u]
        out.append("%d %d" % (ansd[c], ansk[c]))
    sys.stdout.write("\n".join(out) + "\n")

main()

Không gian$O(N + M)$

Thời gian$O(N + M + K^2)$

Cách 3Khi mạng kênh là cây: QHĐ đổi gốc – O(N) · 65%

Khi $M = N - 1$, mạng kênh là một cây: mọi kênh đều xung yếu, mỗi bến là một cụm. Ta cần, với mọi đỉnh $c$, khoảng cách xa nhất $e(c)$ và số đỉnh ở khoảng cách đó – BFS từ từng đỉnh là $O(N^2)$, quá chậm. Đây là bài toán điển hình của QHĐ đổi gốc (rerooting): treo cây ở gốc $1$, mỗi đỉnh lưu một cặp (khoảng cách xa nhất, số đỉnh ở khoảng cách đó).

Lượt 1 (từ lá lên gốc): $dn[c]$ = cặp tốt nhất trong cây con của $c$ (tính cả chính $c$ ở khoảng cách $0$). Mỗi con $y$ cho ứng viên $(dn[y].d + 1,\ dn[y].k)$. Gộp hai ứng viên: lấy khoảng cách lớn hơn, nếu bằng nhau thì cộng số đỉnh.
Lượt 2 (từ gốc xuống lá): $up[y]$ = cặp tốt nhất trong phần cây nằm ngoài cây con của $y$, đo từ $y$. Nó được ghép từ: chính đỉnh cha $c$ (khoảng cách $0$), $up[c]$, và các con khác của $c$ – tất cả rồi cộng thêm $1$.

Bỏ con $y$ ra khỏi "các con khác" trong O(1)

Với mỗi $c$, lưu $b_1$ = (độ sâu lớn nhất từ các con, tổng số đỉnh của mọi con đạt độ sâu đó) và $b_2$ = cặp tương tự cho độ sâu lớn thứ hai (khác $b_1$). Khi bỏ con $y$ có ứng viên $(d_y, k_y)$: nếu $d_y < b_1.d$ thì vẫn là $b_1$; nếu $d_y = b_1.d$ và $b_1.k > k_y$ thì còn $(b_1.d,\ b_1.k - k_y)$ – các con khác cùng độ sâu; còn lại (chỉ $y$ đạt $b_1$) thì lấy $b_2$.

Bẫy "nhất – nhì" theo từng con

Nhiều bạn quen lưu "con tốt nhất" và "con tốt nhì" riêng lẻ. Ở bài đếm này, khi ba con trở lên cùng độ sâu lớn nhất, cách đó làm mất số đỉnh của các con còn lại. Lời giải wrong_top2.cpp mắc đúng lỗi này (xem bảng cuối bài).

Cuối cùng $e(c)$ và số đỉnh là gộp của $b_1[c]$ (các con) và $up[c]$ (phía trên). Không cần tính chính $c$ vì cây có ít nhất 2 đỉnh nên luôn có đỉnh khác xa hơn. Mô phỏng (có thể nhập trọng số – số bến của mỗi cụm – để dùng lại ở Cách 4):

Số đỉnh Các cạnh Trọng số

Ví dụ nhanh:

Với ví dụ "Cây cụm ví dụ 1" (đỉnh 1 là cụm $\{1,2,3\}$, 2 là $\{4\}$, 3 là $\{5\}$, 4 là $\{6,7,8\}$, 5 là $\{9\}$, 6 là $\{10\}$), kết quả trùng với đáp án đề: chẳng hạn đỉnh 1 có cặp $(2, 3)$ nên $a = 5 - 2 = 3$, $b = 3$.

Code Cách 3: nếu $M = N - 1$ thì chạy QHĐ đổi gốc trên chính cây $N$ đỉnh (trọng số $1$), ngược lại dùng Cách 2.

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, long long> PI;   // (khoang cach xa nhat, so ben o khoang cach do)
void add(PI &a, PI b) {            // gop hai ung vien: lay khoang cach lon hon, bang nhau thi cong so ben
    if (b.first > a.first) a = b;
    else if (b.first == a.first) a.second += b.second;
}
// Cach 3: do thi la cay (m = n - 1), moi kenh deu xung yeu -> QHD doi goc tren cay n dinh
void solveTree(int n, vector<vector<pair<int, int>>> &g) {
    vector<int> par(n + 1, -1), order = {1};
    par[1] = 0;
    for (int i = 0; i < (int)order.size(); i++)
        for (auto [y, id] : g[order[i]]) if (par[y] < 0) { par[y] = order[i]; order.push_back(y); }
    const PI NONE = {-1, 0};
    vector<PI> dn(n + 1), b1(n + 1, NONE), b2(n + 1, NONE), up(n + 1, NONE);
    for (int i = n - 1; i >= 0; i--) {
        int c = order[i];
        dn[c] = {0, 1};
        for (auto [y, id] : g[c]) if (y != par[c]) {
            PI cand = {dn[y].first + 1, dn[y].second};
            add(dn[c], cand);
            if (cand.first > b1[c].first) { b2[c] = b1[c]; b1[c] = cand; }
            else if (cand.first == b1[c].first) b1[c].second += cand.second;
            else add(b2[c], cand);
        }
    }
    for (int i = 0; i < n; i++) {
        int c = order[i];
        for (auto [y, id] : g[c]) if (y != par[c]) {
            PI best = {0, 1};
            add(best, up[c]);
            PI my = {dn[y].first + 1, dn[y].second};
            if (my.first == b1[c].first) {
                if (b1[c].second > my.second) add(best, {b1[c].first, b1[c].second - my.second});
                else add(best, b2[c]);
            } else add(best, b1[c]);
            up[y] = {best.first + 1, best.second};
        }
    }
    for (int u = 1; u <= n; u++) {
        PI r = b1[u];
        add(r, up[u]);
        printf("%d %lld\n", n - 1 - r.first, r.second);
    }
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> eu(m), ev(m);
    vector<vector<pair<int, int>>> g(n + 1);           // (ben ke, so hieu kenh)
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &eu[i], &ev[i]);
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    if (m == n - 1) { solveTree(n, g); return 0; }
    // 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    vector<int> tin(n + 1, 0), low(n + 1), pe(n + 1, -1), it(n + 1, 0);
    vector<char> br(m, 0);
    int timer = 0;
    vector<int> st = {1};
    tin[1] = low[1] = ++timer;
    while (!st.empty()) {
        int v = st.back();
        if (it[v] < (int)g[v].size()) {
            auto [to, id] = g[v][it[v]++];
            if (id == pe[v]) continue;
            if (tin[to]) low[v] = min(low[v], tin[to]);
            else { tin[to] = low[to] = ++timer; pe[to] = id; st.push_back(to); }
        } else {
            st.pop_back();
            if (pe[v] >= 0) {
                int p = eu[pe[v]] ^ ev[pe[v]] ^ v;
                low[p] = min(low[p], low[v]);
                if (low[v] > tin[p]) br[pe[v]] = 1;     // kenh pe[v] la kenh xung yeu
            }
        }
    }
    // 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    vector<int> comp(n + 1, -1);
    vector<long long> sz;
    int K = 0;
    for (int s = 1; s <= n; s++) if (comp[s] < 0) {
        comp[s] = K; sz.push_back(0);
        vector<int> q = {s};
        while (!q.empty()) {
            int v = q.back(); q.pop_back(); sz[K]++;
            for (auto [to, id] : g[v]) if (!br[id] && comp[to] < 0) { comp[to] = K; q.push_back(to); }
        }
        K++;
    }
    if (K == 1) {                                       // khong co kenh xung yeu nao
        for (int u = 1; u <= n; u++) printf("0 %d\n", n - 1);
        return 0;
    }
    // 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    vector<vector<int>> t(K);
    for (int i = 0; i < m; i++) if (br[i]) {
        t[comp[eu[i]]].push_back(comp[ev[i]]);
        t[comp[ev[i]]].push_back(comp[eu[i]]);
    }
    int B = K - 1;
    // 4) BFS tu tung cum: tim cum xa nhat va tong so ben cua cac cum xa nhat
    vector<int> fd(K);
    vector<long long> fk(K);
    vector<int> d(K);
    for (int c = 0; c < K; c++) {
        fill(d.begin(), d.end(), -1);
        d[c] = 0;
        vector<int> q = {c};
        for (int i = 0; i < (int)q.size(); i++)
            for (int y : t[q[i]]) if (d[y] < 0) { d[y] = d[q[i]] + 1; q.push_back(y); }
        int mx = 0; long long cnt = 0;
        for (int y = 0; y < K; y++) {
            if (d[y] > mx) { mx = d[y]; cnt = sz[y]; }
            else if (d[y] == mx) cnt += sz[y];
        }
        fd[c] = mx; fk[c] = cnt;
    }
    for (int u = 1; u <= n; u++) {
        int c = comp[u];
        printf("%d %lld\n", B - fd[c], fk[c]);
    }
    return 0;
}

import sys

def solve_tree(n, data):
    # Cach 3: do thi la cay (m = n - 1), moi kenh deu xung yeu -> QHD doi goc tren cay n dinh
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a = int(data[2 + 2 * i]); b = int(data[3 + 2 * i])
        g[a].append(b); g[b].append(a)
    par = [-1] * (n + 1); par[1] = 0
    order = [1]
    for c in order:
        for y in g[c]:
            if par[y] < 0:
                par[y] = c; order.append(y)
    dnd = [0] * (n + 1); dnk = [0] * (n + 1)
    b1d = [-1] * (n + 1); b1k = [0] * (n + 1); b2d = [-1] * (n + 1); b2k = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        c = order[i]
        x1d = -1; x1k = 0; x2d = -1; x2k = 0
        pc = par[c]
        for y in g[c]:
            if y == pc:
                continue
            d = dnd[y] + 1; kk = dnk[y]
            if d > x1d:
                x2d = x1d; x2k = x1k; x1d = d; x1k = kk
            elif d == x1d:
                x1k += kk
            elif d > x2d:
                x2d = d; x2k = kk
            elif d == x2d:
                x2k += kk
        b1d[c] = x1d; b1k[c] = x1k; b2d[c] = x2d; b2k[c] = x2k
        if x1d > 0:
            dnd[c] = x1d; dnk[c] = x1k
        else:
            dnd[c] = 0; dnk[c] = 1
    upd = [-1] * (n + 1); upk = [0] * (n + 1)
    for c in order:
        pc = par[c]
        for y in g[c]:
            if y == pc:
                continue
            bd = 0; bk = 1
            if upd[c] > bd:
                bd = upd[c]; bk = upk[c]
            elif upd[c] == bd:
                bk += upk[c]
            md = dnd[y] + 1; mk = dnk[y]
            if md == b1d[c] and b1k[c] == mk:
                od = b2d[c]; ok = b2k[c]
            elif md == b1d[c]:
                od = md; ok = b1k[c] - mk
            else:
                od = b1d[c]; ok = b1k[c]
            if od > bd:
                bd = od; bk = ok
            elif od == bd:
                bk += ok
            upd[y] = bd + 1; upk[y] = bk
    out = []
    for u in range(1, n + 1):
        d = b1d[u]; kk = b1k[u]
        if upd[u] > d:
            d = upd[u]; kk = upk[u]
        elif upd[u] == d:
            kk += upk[u]
        out.append("%d %d" % (n - 1 - d, kk))
    sys.stdout.write("\n".join(out) + "\n")

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    if m == n - 1:
        solve_tree(n, data)
        return
    eu = [0] * m; ev = [0] * m
    deg = [0] * (n + 2)
    for i in range(m):
        a = int(data[2 + 2 * i]); b = int(data[3 + 2 * i])
        eu[i] = a; ev[i] = b
        deg[a] += 1; deg[b] += 1
    # danh sach ke dang mang phang: ke cua v nam o adj[start[v] : start[v + 1]]
    start = [0] * (n + 2)
    for v in range(1, n + 1):
        start[v + 1] = start[v] + deg[v]
    pos = start[:]
    adj = [0] * (2 * m); aid = [0] * (2 * m)
    for i in range(m):
        a = eu[i]; b = ev[i]
        adj[pos[a]] = b; aid[pos[a]] = i; pos[a] += 1
        adj[pos[b]] = a; aid[pos[b]] = i; pos[b] += 1
    # 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    tin = [0] * (n + 1); low = [0] * (n + 1); pe = [-1] * (n + 1)
    it = start[:]
    br = [0] * m
    timer = 1
    tin[1] = low[1] = 1
    st = [1]
    while st:
        v = st[-1]
        k = it[v]
        if k < start[v + 1]:
            it[v] = k + 1
            to = adj[k]; eid = aid[k]
            if eid == pe[v]:
                continue
            if tin[to]:
                if tin[to] < low[v]:
                    low[v] = tin[to]
            else:
                timer += 1
                tin[to] = low[to] = timer
                pe[to] = eid
                st.append(to)
        else:
            st.pop()
            e = pe[v]
            if e >= 0:
                p = eu[e] ^ ev[e] ^ v
                if low[v] < low[p]:
                    low[p] = low[v]
                if low[v] > tin[p]:
                    br[e] = 1                  # kenh e la kenh xung yeu
    # 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    comp = [-1] * (n + 1)
    sz = []
    K = 0
    for s in range(1, n + 1):
        if comp[s] >= 0:
            continue
        comp[s] = K
        q = [s]; cnt = 0
        while q:
            v = q.pop(); cnt += 1
            for k in range(start[v], start[v + 1]):
                to = adj[k]
                if comp[to] < 0 and not br[aid[k]]:
                    comp[to] = K
                    q.append(to)
        sz.append(cnt)
        K += 1
    if K == 1:                                 # khong co kenh xung yeu nao
        sys.stdout.write(("0 %d\n" % (n - 1)) * n)
        return
    # 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    t = [[] for _ in range(K)]
    for i in range(m):
        if br[i]:
            a = comp[eu[i]]; b = comp[ev[i]]
            t[a].append(b); t[b].append(a)
    B = K - 1
    # 4) BFS tu tung cum: tim cum xa nhat va tong so ben cua cac cum xa nhat
    ansd = [0] * K; ansk = [0] * K
    for c in range(K):
        d = [-1] * K
        d[c] = 0
        q = [c]
        for x in q:
            dx = d[x] + 1
            for y in t[x]:
                if d[y] < 0:
                    d[y] = dx
                    q.append(y)
        mx = d[q[-1]]                          # BFS: dinh cuoi cung co khoang cach lon nhat
        cnt = 0
        for y in q:
            if d[y] == mx:
                cnt += sz[y]
        ansd[c] = B - mx; ansk[c] = cnt
    out = []
    for u in range(1, n + 1):
        c = comp[u]
        out.append("%d %d" % (ansd[c], ansk[c]))
    sys.stdout.write("\n".join(out) + "\n")

main()

Không gian$O(N + M)$

Thời gian$O(N)$ khi là cây, $O(N + M + K^2)$ trong trường hợp còn lại

Cách 4Tarjan + cây cụm + QHĐ đổi gốc có trọng số – O(N + M) · 100%

Ghép hai mảnh lại: Tarjan khử đệ quy tìm cầu, gom cụm (trọng số mỗi cụm = số bến), dựng cây cụm, rồi chạy QHĐ đổi gốc của Cách 3 với trọng số $sz[c]$ thay cho $1$. Đáp án của bến $u$ là đáp án của cụm chứa nó. Nhớ xử lý riêng trường hợp không có cầu nào ($K = 1$): khi đó mọi bến $v \ne u$ đều được, $b_u = N - 1$ chứ không phải $N$ (lời giải wrong_self.cpp quên điều này).

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, long long> PI;   // (khoang cach xa nhat, so ben o khoang cach do)
void add(PI &a, PI b) {            // gop hai ung vien: lay khoang cach lon hon, bang nhau thi cong so ben
    if (b.first > a.first) a = b;
    else if (b.first == a.first) a.second += b.second;
}
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> eu(m), ev(m);
    vector<vector<pair<int, int>>> g(n + 1);           // (ben ke, so hieu kenh)
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &eu[i], &ev[i]);
        g[eu[i]].push_back({ev[i], i});
        g[ev[i]].push_back({eu[i], i});
    }
    // 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    vector<int> tin(n + 1, 0), low(n + 1), pe(n + 1, -1), it(n + 1, 0);
    vector<char> br(m, 0);
    int timer = 0;
    vector<int> st = {1};
    tin[1] = low[1] = ++timer;
    while (!st.empty()) {
        int v = st.back();
        if (it[v] < (int)g[v].size()) {
            auto [to, id] = g[v][it[v]++];
            if (id == pe[v]) continue;
            if (tin[to]) low[v] = min(low[v], tin[to]);
            else { tin[to] = low[to] = ++timer; pe[to] = id; st.push_back(to); }
        } else {
            st.pop_back();
            if (pe[v] >= 0) {
                int p = eu[pe[v]] ^ ev[pe[v]] ^ v;
                low[p] = min(low[p], low[v]);
                if (low[v] > tin[p]) br[pe[v]] = 1;     // kenh pe[v] la kenh xung yeu
            }
        }
    }
    // 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    vector<int> comp(n + 1, -1);
    vector<long long> sz;
    int K = 0;
    for (int s = 1; s <= n; s++) if (comp[s] < 0) {
        comp[s] = K; sz.push_back(0);
        vector<int> q = {s};
        while (!q.empty()) {
            int v = q.back(); q.pop_back(); sz[K]++;
            for (auto [to, id] : g[v]) if (!br[id] && comp[to] < 0) { comp[to] = K; q.push_back(to); }
        }
        K++;
    }
    if (K == 1) {                                       // khong co kenh xung yeu nao
        for (int u = 1; u <= n; u++) printf("0 %d\n", n - 1);
        return 0;
    }
    // 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    vector<vector<int>> t(K);
    for (int i = 0; i < m; i++) if (br[i]) {
        t[comp[eu[i]]].push_back(comp[ev[i]]);
        t[comp[ev[i]]].push_back(comp[eu[i]]);
    }
    int B = K - 1;
    vector<int> par(K, -1), order = {0};
    par[0] = 0;
    for (int i = 0; i < (int)order.size(); i++)
        for (int y : t[order[i]]) if (par[y] < 0) { par[y] = order[i]; order.push_back(y); }
    par[0] = -1;
    // 4) QHD doi goc. dn[c]: xa nhat trong cay con c (tinh ca c). b1, b2: hai muc sau khac nhau tot nhat tu cac con
    const PI NONE = {-1, 0};
    vector<PI> dn(K), b1(K, NONE), b2(K, NONE), up(K, NONE);
    for (int i = K - 1; i >= 0; i--) {
        int c = order[i];
        dn[c] = {0, sz[c]};
        for (int y : t[c]) if (y != par[c]) {
            PI cand = {dn[y].first + 1, dn[y].second};
            add(dn[c], cand);
            if (cand.first > b1[c].first) { b2[c] = b1[c]; b1[c] = cand; }
            else if (cand.first == b1[c].first) b1[c].second += cand.second;
            else add(b2[c], cand);
        }
    }
    for (int i = 0; i < K; i++) {
        int c = order[i];
        for (int y : t[c]) if (y != par[c]) {
            PI best = {0, sz[c]};                       // chinh cum c
            add(best, up[c]);                           // phia tren c
            PI my = {dn[y].first + 1, dn[y].second};    // cac con khac y
            if (my.first == b1[c].first) {
                if (b1[c].second > my.second) add(best, {b1[c].first, b1[c].second - my.second});
                else add(best, b2[c]);
            } else add(best, b1[c]);
            up[y] = {best.first + 1, best.second};
        }
    }
    for (int u = 1; u <= n; u++) {
        int c = comp[u];
        PI r = b1[c];
        add(r, up[c]);
        printf("%d %lld\n", B - r.first, r.second);
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); m = int(data[1])
    eu = [0] * m; ev = [0] * m
    deg = [0] * (n + 2)
    for i in range(m):
        a = int(data[2 + 2 * i]); b = int(data[3 + 2 * i])
        eu[i] = a; ev[i] = b
        deg[a] += 1; deg[b] += 1
    # danh sach ke dang mang phang: ke cua v nam o adj[start[v] : start[v + 1]]
    start = [0] * (n + 2)
    for v in range(1, n + 1):
        start[v + 1] = start[v] + deg[v]
    pos = start[:]
    adj = [0] * (2 * m); aid = [0] * (2 * m)
    for i in range(m):
        a = eu[i]; b = ev[i]
        adj[pos[a]] = b; aid[pos[a]] = i; pos[a] += 1
        adj[pos[b]] = a; aid[pos[b]] = i; pos[b] += 1
    # 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha
    tin = [0] * (n + 1); low = [0] * (n + 1); pe = [-1] * (n + 1)
    it = start[:]
    br = [0] * m
    timer = 1
    tin[1] = low[1] = 1
    st = [1]
    while st:
        v = st[-1]
        k = it[v]
        if k < start[v + 1]:
            it[v] = k + 1
            to = adj[k]; eid = aid[k]
            if eid == pe[v]:
                continue
            if tin[to]:
                if tin[to] < low[v]:
                    low[v] = tin[to]
            else:
                timer += 1
                tin[to] = low[to] = timer
                pe[to] = eid
                st.append(to)
        else:
            st.pop()
            e = pe[v]
            if e >= 0:
                p = eu[e] ^ ev[e] ^ v
                if low[v] < low[p]:
                    low[p] = low[v]
                if low[v] > tin[p]:
                    br[e] = 1                  # kenh e la kenh xung yeu
    # 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"
    comp = [-1] * (n + 1)
    sz = []
    K = 0
    for s in range(1, n + 1):
        if comp[s] >= 0:
            continue
        comp[s] = K
        q = [s]; cnt = 0
        while q:
            v = q.pop(); cnt += 1
            for k in range(start[v], start[v + 1]):
                to = adj[k]
                if comp[to] < 0 and not br[aid[k]]:
                    comp[to] = K
                    q.append(to)
        sz.append(cnt)
        K += 1
    if K == 1:                                 # khong co kenh xung yeu nao
        sys.stdout.write(("0 %d\n" % (n - 1)) * n)
        return
    # 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum
    t = [[] for _ in range(K)]
    for i in range(m):
        if br[i]:
            a = comp[eu[i]]; b = comp[ev[i]]
            t[a].append(b); t[b].append(a)
    B = K - 1
    par = [-1] * K
    par[0] = 0
    order = [0]
    for c in order:
        for y in t[c]:
            if par[y] < 0:
                par[y] = c
                order.append(y)
    par[0] = -1
    # 4) QHD doi goc: dn = xa nhat trong cay con (tinh ca c); (b1d, b1k), (b2d, b2k): hai muc sau khac nhau tot nhat tu cac con
    dnd = [0] * K; dnk = [0] * K
    b1d = [-1] * K; b1k = [0] * K; b2d = [-1] * K; b2k = [0] * K
    for i in range(K - 1, -1, -1):
        c = order[i]
        x1d = -1; x1k = 0; x2d = -1; x2k = 0
        pc = par[c]
        for y in t[c]:
            if y == pc:
                continue
            d = dnd[y] + 1; kk = dnk[y]
            if d > x1d:
                x2d = x1d; x2k = x1k; x1d = d; x1k = kk
            elif d == x1d:
                x1k += kk
            elif d > x2d:
                x2d = d; x2k = kk
            elif d == x2d:
                x2k += kk
        b1d[c] = x1d; b1k[c] = x1k; b2d[c] = x2d; b2k[c] = x2k
        if x1d > 0:
            dnd[c] = x1d; dnk[c] = x1k
        else:
            dnd[c] = 0; dnk[c] = sz[c]
    upd = [-1] * K; upk = [0] * K
    for c in order:
        pc = par[c]
        for y in t[c]:
            if y == pc:
                continue
            bd = 0; bk = sz[c]                 # chinh cum c
            if upd[c] > bd:                    # phia tren c
                bd = upd[c]; bk = upk[c]
            elif upd[c] == bd:
                bk += upk[c]
            md = dnd[y] + 1; mk = dnk[y]       # cac con khac y
            if md == b1d[c] and b1k[c] == mk:
                od = b2d[c]; ok = b2k[c]
            elif md == b1d[c]:
                od = md; ok = b1k[c] - mk
            else:
                od = b1d[c]; ok = b1k[c]
            if od > bd:
                bd = od; bk = ok
            elif od == bd:
                bk += ok
            upd[y] = bd + 1; upk[y] = bk
    ansd = [0] * K; ansk = [0] * K
    for c in range(K):
        d = b1d[c]; kk = b1k[c]
        if upd[c] > d:
            d = upd[c]; kk = upk[c]
        elif upd[c] == d:
            kk += upk[c]
        ansd[c] = B - d; ansk[c] = kk
    out = []
    for u in range(1, n + 1):
        c = comp[u]
        out.append("%d %d" % (ansd[c], ansk[c]))
    sys.stdout.write("\n".join(out) + "\n")

main()

Không gian$O(N + M)$

Thời gian$O(N + M)$

C++▶ Chạy tay từng dòng codeTheo dõi Tarjan khử đệ quy, gom cụm, dựng cây cụm và hai lượt QHĐ đổi gốc.

Dữ liệu vào (stdin) – sửa thoải mái

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef pair<int, long long> PI; // (khoang cach xa nhat, so ben o khoang cach do)

4void add(PI &a, PI b) { // gop hai ung vien: lay khoang cach lon hon, bang nhau thi cong so ben

5 if (b.first > a.first) a = b;

6 else if (b.first == a.first) a.second += b.second;

8int main() {

9 int n, m;

10 scanf("%d %d", &n, &m);

11 vector<int> eu(m), ev(m);

12 vector<vector<pair<int, int>>> g(n + 1); // (ben ke, so hieu kenh)

13 for (int i = 0; i < m; i++) {

14 scanf("%d %d", &eu[i], &ev[i]);

15 g[eu[i]].push_back({ev[i], i});

16 g[ev[i]].push_back({eu[i], i});

17 }

18 // 1) Tim cau bang Tarjan (khu de quy), bo qua dung KENH vua di toi chu khong bo qua dinh cha

19 vector<int> tin(n + 1, 0), low(n + 1), pe(n + 1, -1), it(n + 1, 0);

20 vector<char> br(m, 0);

21 int timer = 0;

22 vector<int> st = {1};

23 tin[1] = low[1] = ++timer;

24 while (!st.empty()) {

25 int v = st.back();

26 if (it[v] < (int)g[v].size()) {

27 auto [to, id] = g[v][it[v]++];

28 if (id == pe[v]) continue;

29 if (tin[to]) low[v] = min(low[v], tin[to]);

30 else { tin[to] = low[to] = ++timer; pe[to] = id; st.push_back(to); }

31 } else {

32 st.pop_back();

33 if (pe[v] >= 0) {

34 int p = eu[pe[v]] ^ ev[pe[v]] ^ v;

35 low[p] = min(low[p], low[v]);

36 if (low[v] > tin[p]) br[pe[v]] = 1; // kenh pe[v] la kenh xung yeu

37 }

38 }

39 }

40 // 2) Gom cac ben noi voi nhau khong qua kenh xung yeu thanh mot "cum"

41 vector<int> comp(n + 1, -1);

42 vector<long long> sz;

43 int K = 0;

44 for (int s = 1; s <= n; s++) if (comp[s] < 0) {

45 comp[s] = K; sz.push_back(0);

46 vector<int> q = {s};

47 while (!q.empty()) {

48 int v = q.back(); q.pop_back(); sz[K]++;

49 for (auto [to, id] : g[v]) if (!br[id] && comp[to] < 0) { comp[to] = K; q.push_back(to); }

50 }

51 K++;

52 }

53 if (K == 1) { // khong co kenh xung yeu nao

54 for (int u = 1; u <= n; u++) printf("0 %d\n", n - 1);

55 return 0;

56 }

57 // 3) Cay cac cum: canh = kenh xung yeu, trong so dinh = so ben trong cum

58 vector<vector<int>> t(K);

59 for (int i = 0; i < m; i++) if (br[i]) {

60 t[comp[eu[i]]].push_back(comp[ev[i]]);

61 t[comp[ev[i]]].push_back(comp[eu[i]]);

62 }

63 int B = K - 1;

64 vector<int> par(K, -1), order = {0};

65 par[0] = 0;

66 for (int i = 0; i < (int)order.size(); i++)

67 for (int y : t[order[i]]) if (par[y] < 0) { par[y] = order[i]; order.push_back(y); }

68 par[0] = -1;

69 // 4) QHD doi goc. dn[c]: xa nhat trong cay con c (tinh ca c). b1, b2: hai muc sau khac nhau tot nhat tu cac con

70 const PI NONE = {-1, 0};

71 vector<PI> dn(K), b1(K, NONE), b2(K, NONE), up(K, NONE);

72 for (int i = K - 1; i >= 0; i--) {

73 int c = order[i];

74 dn[c] = {0, sz[c]};

75 for (int y : t[c]) if (y != par[c]) {

76 PI cand = {dn[y].first + 1, dn[y].second};

77 add(dn[c], cand);

78 if (cand.first > b1[c].first) { b2[c] = b1[c]; b1[c] = cand; }

79 else if (cand.first == b1[c].first) b1[c].second += cand.second;

80 else add(b2[c], cand);

81 }

82 }

83 for (int i = 0; i < K; i++) {

84 int c = order[i];

85 for (int y : t[c]) if (y != par[c]) {

86 PI best = {0, sz[c]}; // chinh cum c

87 add(best, up[c]); // phia tren c

88 PI my = {dn[y].first + 1, dn[y].second}; // cac con khac y

89 if (my.first == b1[c].first) {

90 if (b1[c].second > my.second) add(best, {b1[c].first, b1[c].second - my.second});

91 else add(best, b2[c]);

92 } else add(best, b1[c]);

93 up[y] = {best.first + 1, best.second};

94 }

95 }

96 for (int u = 1; u <= n; u++) {

97 int c = comp[u];

98 PI r = b1[c];

99 add(r, up[c]);

100 printf("%d %lld\n", B - r.first, r.second);

101 }

102 return 0;

103}

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 37 test: subtask 1 (10 test, $N \le 300$: hai ví dụ, $N = 2$ có/không kênh song song, đồ thị không có cầu, cây cụm ngẫu nhiên, hình nhện, hai nhện nối nhau, tam phân, đường thẳng), subtask 2 (8 test, $N = 5000$), subtask 3 (9 cây $N \approx 2\cdot 10^5$: ngẫu nhiên, đường thẳng, hình sao, nhị phân, nhện nhiều chân dài bằng nhau, hai nhện nối nhau (đường kính lẻ), chổi, sâu róm, cây tam phân), subtask 4 (10 test $N = 2\cdot 10^5$, $M \le 3\cdot 10^5$, từ $7{,}5\cdot 10^4$ tới $9 \cdot 10^4$ cụm, cụm ở lá thường có nhiều bến, khoảng 5% kênh nối cụm được nhân đôi thành kênh song song).

Cách làm	Sub 1 (15%)	Sub 2 (25%)	Sub 3 (25%)	Sub 4 (35%)	Điểm
Cách 1 – Thử mọi kênh mới, đếm cầu bằng Tarjan	Đúng	TLE	TLE/RE	TLE	15
Cách 2 – Tarjan + BFS từ từng cụm	Đúng	Đúng	TLE	TLE	40
Cách 3 – Cách 2 + QHĐ đổi gốc khi là cây	Đúng	Đúng	Đúng	TLE	65
Cách 4 – Tarjan + cây cụm + QHĐ đổi gốc (sol.cpp)	Đúng	Đúng	Đúng	Đúng	100
Sai: Tarjan bỏ qua đỉnh cha thay vì đúng kênh (kênh song song)	5/10 (WA)	1/8 (WA)	Đúng	WA	35,6
Sai: đếm số cụm xa nhất thay vì số bến	7/10 (WA)	2/8 (WA)	Đúng	WA	41,8
Sai: không có cầu thì in N thay vì N − 1	8/10 (WA)	7/8 (WA)	Đúng	Đúng	93,9
Sai: đổi gốc chỉ giữ con nhất/nhì riêng lẻ	8/10 (WA)	4/8 (WA)	5/9 (WA)	4/10 (WA)	52,4

Lỗi "quên trường hợp không có cầu" chỉ bị bắt ở subtask 1 và 2: đồ thị không có cầu thì Cách 2 cũng chạy rất nhanh, nên không thể đặt test như vậy vào subtask 4 (mọi test subtask 4 phải làm Cách 2, Cách 3 bị TLE). Mất ít điểm nhưng vẫn là mất điểm oan!

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: sub1.cpp được 15 điểm; sub2.cpp được 40 điểm; sub3.cpp được 65 điểm; sol.cpp được 100 điểm; wrong_parent.cpp được 35,6 điểm; wrong_comps.cpp được 41,8 điểm; wrong_self.cpp được 93,9 điểm; wrong_top2.cpp được 52,4 điểm. Lời giải chuẩn sol.cpp chạy test lâu nhất khoảng 0,35 giây (thời gian CPU), bản Python sol.py cho cùng đáp án trên mọi test (trên CPython chậm hơn nhiều, các em nhớ chọn PyPy 3 khi nộp). "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Lập Trình Thuật Toán

Đào kênh (Đề tự luyện HSG Tin quốc gia – Bài 2)

Đề bài

Lời mở đầu

Cách 1Thử mọi kênh mới – O(N² (N + M)) · 15%

Cách 2Tarjan một lần + BFS trên cây cụm – O(N + M + K²) · 40%

Cách 3Khi mạng kênh là cây: QHĐ đổi gốc – O(N) · 65%

Cách 4Tarjan + cây cụm + QHĐ đổi gốc có trọng số – O(N + M) · 100%

Bộ test chấm "bắt" những lỗi nào?

Nhận xét

Đăng nhận xét

Dữ liệu trang web (tự động – không xoá)

Hướng dẫn tham gia Thi thử HSG Tin học hàng tuần trên ClueOJ (từ đăng ký tài khoản đến lúc vào phòng thi)

Khóa học luyện thi chuyên Tin, HSG Tin học – lập trình thuật toán C++