Cầu khỉ (Đề tự luyện HSG Tin 12 – Bài 4)
Đề bài
Cầu khỉ. Cù lao có $N$ ấp. Trong $Q$ ngày, mỗi ngày thầy Sơn lập một phương án bắc cầu khỉ — một danh sách các cây cầu xếp theo thứ tự thêm vào. Phương án ngày $0$ rỗng. Phương án ngày $i$ được lập theo một trong ba cách:
1 u v: lấy phương án ngày $i-1$, thêm vào cuối cây cầu nối ấp $u$ và ấp $v$ ($u \ne v$, có thể đã đi lại được từ trước);2 t: lấy phương án ngày $i-1$, bỏ đi $t$ cây cầu được thêm sau cùng;3 k: lấy lại y nguyên phương án của ngày $k$ ($0 \le k < i$).
Sau mỗi ngày, in số cặp ấp $\{x, y\}$ ($x < y$) đi lại được với nhau bằng các cầu của phương án ngày đó.
Dữ liệu vào: dòng đầu $N, Q$ ($2 \le N \le 2 \cdot 10^5$, $1 \le Q \le 2 \cdot 10^5$); $Q$ dòng sau, mỗi dòng một thao tác như trên.
Kết quả: $Q$ dòng, dòng thứ $i$ là số cặp ấp đi lại được theo phương án ngày $i$.
- Subtask 1 (20%): $N, Q \le 2000$.
- Subtask 2 (20%): chỉ có thao tác
1. - Subtask 3 (25%): chỉ có thao tác
1và2. - Subtask 4 (35%): không có ràng buộc gì thêm.
5 8
1 1 2
1 2 3
1 4 5
2 2
3 3
1 3 1
2 3
3 51
3
4
1
4
4
1
4Ngày 3 có các nhóm $\{1,2,3\}$ và $\{4,5\}$ nên có $3+1=4$ cặp. Ngày 4 bỏ 2 cầu sau cùng, chỉ còn cầu (1–2): 1 cặp. Ngày 5 lấy lại phương án ngày 3. Ngày 6 thêm cầu (3–1) nhưng ấp 1 và 3 vốn đã đi lại được nên vẫn 4 cặp. Ngày 7 bỏ 3 cầu sau cùng (3–1), (4–5), (2–3), còn 1 cặp. Ngày 8 lấy lại phương án ngày 5.
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 Cầu khỉLời mở đầu
Đọc đề lần đầu, các bạn sẽ thấy bài này "giống giống" bài DSU quen thuộc: thêm cạnh, hỏi số cặp đỉnh liên thông. Cái khó nằm ở hai thao tác còn lại: bỏ đi $t$ cầu sau cùng và nhất là quay về phương án của một ngày bất kỳ trong quá khứ. DSU thì "nối" rất giỏi, còn "cắt" thì chịu. Ta hãy gỡ từng nút thắt một.
Nhận xét 1 – đếm số cặp. Nếu các ấp chia thành các nhóm liên thông có kích thước $s_1, s_2, \dots$ thì số cặp đi lại được là $\sum \binom{s_j}{2}$. Khi một cây cầu nối hai nhóm khác nhau kích thước $A$ và $B$, số cặp tăng đúng $A \cdot B$ (mỗi ấp bên này ghép với mỗi ấp bên kia). Cầu nối hai ấp đã cùng nhóm thì không làm thay đổi gì. Số cặp có thể lên tới $\binom{2 \cdot 10^5}{2} \approx 2 \cdot 10^{10}$ nên phải dùng long long.
Nhận xét 2 – phương án là một ngăn xếp. Thao tác 1 là "đẩy" một cầu vào cuối danh sách, thao tác 2 là "lấy ra" $t$ cầu ở cuối. Vậy mỗi phương án giống như một ngăn xếp cầu. Thao tác 3 thì cho phép nhảy về một ngăn xếp cũ bất kỳ.
Nhận xét 3 – cây phương án. Hãy vẽ mọi danh sách cầu từng xuất hiện thành một cây: gốc là danh sách rỗng, mỗi lần thao tác 1 sinh ra một nút con (danh sách cha + 1 cầu ở cuối). Khi đó danh sách cầu của một nút chính là các cầu trên đường đi từ gốc xuống nút đó. Thao tác 2 với $t$ = đi lên tổ tiên thứ $t$; thao tác 3 = dùng lại đúng nút của ngày $k$. Mỗi ngày chỉ cần nhớ nó "đứng ở nút nào".
Cây phương án của ví dụ: chỉ 4 thao tác loại 1 nên chỉ có 4 nút ngoài gốc. Tám ngày chỉ "đứng" ở các nút này, và đáp án của ngày = giá trị val của nút nó đứng.
Bốn subtask ứng với bốn cách làm, mỗi cách gỡ thêm một nút thắt:
Cách 1Chép nguyên danh sách, dựng lại DSU – O(Q·(N+Q)) · 20%
Cách "thật thà" nhất: làm đúng như đề nói. Lưu hẳn danh sách cầu của từng ngày vào plan[i]:
- thao tác 1:
plan[i] = plan[i-1]rồi thêm cầu $(u, v)$ vào cuối; - thao tác 2:
plan[i] = plan[i-1]rồi cắt bớt $t$ phần tử cuối; - thao tác 3:
plan[i] = plan[k].
Sau đó dựng DSU từ đầu với các cầu của plan[i], mỗi lần ghép hai nhóm kích thước $A, B$ thì cộng $A \cdot B$ vào đáp án (Nhận xét 1). Mỗi ngày tốn $O(N + Q)$ (danh sách dài tối đa $Q$), tổng $O(Q \cdot (N + Q))$ — với $N, Q \le 2000$ chỉ khoảng $8 \cdot 10^6$ phép tính, chạy vèo vèo.
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int findRoot(int x) {
while (par[x] != x) x = par[x] = par[par[x]];
return x;
}
int main() {
int n, q;
cin >> n >> q;
vector<vector<pair<int,int>>> plan(q + 1); // plan[i] = danh sach cau ngay i
for (int i = 1; i <= q; i++) {
int type;
cin >> type;
if (type == 1) {
int u, v;
cin >> u >> v;
plan[i] = plan[i - 1];
plan[i].push_back({u, v});
} else if (type == 2) {
int t;
cin >> t;
plan[i] = plan[i - 1];
plan[i].resize(plan[i].size() - t);
} else {
int k;
cin >> k;
plan[i] = plan[k];
}
// dung lai DSU tu dau cho phuong an ngay i
for (int x = 1; x <= n; x++) { par[x] = x; sz[x] = 1; }
long long pairs = 0;
for (auto &e : plan[i]) {
int a = findRoot(e.first), b = findRoot(e.second);
if (a == b) continue;
pairs += (long long)sz[a] * sz[b];
par[b] = a; sz[a] += sz[b];
}
cout << pairs << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
plan = [[] for _ in range(q + 1)] # plan[i] = danh sach cau ngay i
pos = 2
out = []
for i in range(1, q + 1):
typ = data[pos]
if typ == b'1':
u = int(data[pos + 1]); v = int(data[pos + 2]); pos += 3
plan[i] = plan[i - 1] + [(u, v)]
elif typ == b'2':
t = int(data[pos + 1]); pos += 2
plan[i] = plan[i - 1][:len(plan[i - 1]) - t]
else:
k = int(data[pos + 1]); pos += 2
plan[i] = plan[k]
# dung lai DSU tu dau cho phuong an ngay i
par = list(range(n + 1))
sz = [1] * (n + 1)
pairs = 0
for u, v in plan[i]:
while par[u] != u:
par[u] = par[par[u]]; u = par[u]
while par[v] != v:
par[v] = par[par[v]]; v = par[v]
if u != v:
pairs += sz[u] * sz[v]
par[v] = u; sz[u] += sz[v]
out.append(pairs)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()Cách 2Chỉ có thao tác thêm cầu – DSU thường – O(Q·α(N)) · 20%
Ở subtask 2 chỉ có thao tác 1 u v: phương án ngày $i$ = phương án ngày $i - 1$ + một cầu. Đây đúng là bài DSU kinh điển. Ta giữ một DSU duy nhất, mỗi ngày gọi ghép $u$ với $v$:
- tìm gốc $a$ của $u$, gốc $b$ của $v$;
- nếu $a = b$: cầu thừa, đáp án giữ nguyên;
- nếu $a \ne b$: đáp án cộng thêm
sz[a] * sz[b], rồi gắn nhóm nhỏ vào nhóm lớn.
Ví dụ: 5 ấp, các cầu (1–2), (2–3), (4–5), (3–5). Đáp án lần lượt: $1$; $1 + 2 \cdot 1 = 3$; $3 + 1 \cdot 1 = 4$; $4 + 3 \cdot 2 = 10$ (cả 5 ấp một nhóm, đúng bằng $\binom{5}{2} = 10$).
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int findRoot(int x) {
while (par[x] != x) x = par[x] = par[par[x]];
return x;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int x = 1; x <= n; x++) { par[x] = x; sz[x] = 1; }
long long pairs = 0;
for (int i = 1; i <= q; i++) {
int type, u, v = 0;
scanf("%d %d", &type, &u);
if (type == 1) {
scanf("%d", &v);
int a = findRoot(u), b = findRoot(v);
if (a != b) {
if (sz[a] < sz[b]) swap(a, b);
pairs += (long long)sz[a] * sz[b]; // ghep 2 nhom: them sz[a]*sz[b] cap
par[b] = a; sz[a] += sz[b];
}
}
// (thao tac 2, 3 khong xu ly duoc o cach nay)
printf("%lld\n", pairs);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
pairs = 0
out = []
pos = 2
for _ in range(q):
if data[pos] == b'1':
u = int(data[pos + 1]); v = int(data[pos + 2]); pos += 3
while par[u] != u:
par[u] = par[par[u]]; u = par[u]
while par[v] != v:
par[v] = par[par[v]]; v = par[v]
if u != v:
if sz[u] < sz[v]:
u, v = v, u
pairs += sz[u] * sz[v] # ghep 2 nhom: them sz[u]*sz[v] cap
par[v] = u; sz[u] += sz[v]
else:
pos += 2 # thao tac 2, 3 khong xu ly duoc o cach nay
out.append(pairs)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()int. Nhiều test có nhóm lớn hơn $65\,536$ ấp, nên ai để biến đếm là int sẽ mất điểm (xem bảng cuối bài).Cách 3Thêm và bỏ cầu sau cùng – DSU hoàn tác – O(Q·log N) · 45%
Subtask 3 có thêm thao tác 2 t. Điểm mấu chốt: cầu bị bỏ luôn là cầu mới nhất. Mà DSU tuy không biết "cắt cạnh bất kỳ", nhưng hoàn toàn có thể hoàn tác thao tác ghép gần nhất — y như nút Undo (Ctrl+Z) — nếu ta ghi lại mỗi lần ghép đã thay đổi những gì.
Để hoàn tác được, DSU phải đổi hai chỗ so với Cách 2:
- Không nén đường đi (path compression). Nén đường làm thay đổi
parcủa rất nhiều đỉnh, không ghi lại nổi. Bù lại ta gắn nhóm nhỏ vào nhóm lớn (union by size), khi đó cây DSU cao không quá $\log_2 N$, nên hàm tìm gốc vẫn chỉ tốn $O(\log N)$. - Mỗi lần ghép chỉ thay đổi đúng hai thứ:
par[b] = avàsz[a] += sz[b]. Ta đẩy $b$ vào ngăn xếp lịch sửhist. Khi hoàn tác: lấy $b$ ra, $a = $par[b], trả lạisz[a] -= sz[b], trừ đáp án đisz[a] * sz[b], đặt lạipar[b] = b.
-1 ("cầu này không đổi gì") vào hist.Các bạn thử tự bấm mô phỏng dưới đây (chỉ gồm thao tác 1 và 2) để thấy ngăn xếp lịch sử hoạt động. Chú ý ngày có cầu thừa.
#include <bits/stdc++.h>
using namespace std;
int par[200005], sz[200005];
int findRoot(int x) { // KHONG nen duong di de con hoan tac duoc
while (par[x] != x) x = par[x];
return x;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
for (int x = 1; x <= n; x++) { par[x] = x; sz[x] = 1; }
long long pairs = 0;
vector<int> hist; // moi cau da them -> goc bi gan vao (hoac -1)
for (int i = 1; i <= q; i++) {
int type, x;
scanf("%d %d", &type, &x);
if (type == 1) {
int y;
scanf("%d", &y);
int a = findRoot(x), b = findRoot(y);
if (a == b) hist.push_back(-1); // cau thua: van phai ghi lai!
else {
if (sz[a] < sz[b]) swap(a, b);
pairs += (long long)sz[a] * sz[b];
par[b] = a; sz[a] += sz[b];
hist.push_back(b);
}
} else if (type == 2) {
for (int z = 0; z < x; z++) { // hoan tac x cau sau cung
int b = hist.back(); hist.pop_back();
if (b == -1) continue;
int a = par[b];
sz[a] -= sz[b];
pairs -= (long long)sz[a] * sz[b];
par[b] = b;
}
}
// (thao tac 3 khong xu ly duoc o cach nay)
printf("%lld\n", pairs);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
par = list(range(n + 1))
sz = [1] * (n + 1)
pairs = 0
hist = [] # moi cau da them -> goc bi gan vao (hoac -1)
out = []
pos = 2
for _ in range(q):
typ = data[pos]
if typ == b'1':
a = int(data[pos + 1]); b = int(data[pos + 2]); pos += 3
while par[a] != a: # KHONG nen duong di de con hoan tac duoc
a = par[a]
while par[b] != b:
b = par[b]
if a == b:
hist.append(-1) # cau thua: van phai ghi lai!
else:
if sz[a] < sz[b]:
a, b = b, a
pairs += sz[a] * sz[b]
par[b] = a; sz[a] += sz[b]
hist.append(b)
elif typ == b'2':
t = int(data[pos + 1]); pos += 2
for _ in range(t): # hoan tac t cau sau cung
b = hist.pop()
if b == -1:
continue
a = par[b]
sz[a] -= sz[b]
pairs -= sz[a] * sz[b]
par[b] = b
else:
pos += 2 # thao tac 3 khong xu ly duoc o cach nay
out.append(pairs)
sys.stdout.write('\n'.join(map(str, out)) + '\n')
main()2 t có thể tốn $t$ bước hoàn tác, nhưng mỗi cầu chỉ được đẩy vào một lần và lấy ra tối đa một lần, nên tổng số bước hoàn tác trong cả bài không vượt quá $Q$ (phân tích khấu hao).Cách này đúng cho subtask 2 và 3 (45%). Nhưng gặp 3 k thì bó tay: phương án ngày $k$ có thể nằm ở một "nhánh" đã bị hoàn tác từ lâu, ngăn xếp hiện tại không còn giữ nó nữa. Khấu hao cũng sụp đổ: nếu cứ lặp "quay về phương án $10^5$ cầu" rồi "bỏ $10^5$ cầu" thì phải dựng lại / hoàn tác $10^5$ cầu mỗi lần.
Cách 4Cây phương án + nhảy nhị phân + DFS hoàn tác – O((N+Q)·log N) · 100%
Bí quyết là xử lý offline: đề không bắt ta trả lời ngay sau mỗi ngày, nên cứ đọc hết $Q$ thao tác, dựng xong cây phương án (Nhận xét 3) rồi mới tính.
Bước 1 – Dựng cây phương án
Nút $0$ là phương án rỗng. Ta lưu at[i] = nút mà ngày $i$ "đứng", at[0] = 0.
1 u v: tạo nút mới $x$, cha làat[i-1], ghi cầu của nút là $(u, v)$, độ sâudep[x] = dep[cha] + 1;at[i] = x.2 t:at[i]= tổ tiên thứ $t$ củaat[i-1](bỏ $t$ cầu cuối = đi lên $t$ bậc).3 k:at[i] = at[k]. Không tạo gì mới cả!
Cây có tối đa $Q + 1$ nút. Riêng thao tác 2 cần tìm tổ tiên thứ $t$ thật nhanh. Leo từng bậc thì tốn $O(t)$ — và như đã nói, có thể lặp lại $10^5$ lần với $t \approx 10^5$. Ta dùng nhảy nhị phân: up[j][x] = tổ tiên thứ $2^j$ của $x$, tính ngay khi tạo nút: up[j][x] = up[j-1][ up[j-1][x] ] (cha của nút đã có sẵn bảng vì được tạo trước). Muốn leo $t$ bậc thì phân tích $t$ ra nhị phân, bit $j$ nào bật thì nhảy x = up[j][x]. Ví dụ $t = 13 = 8 + 4 + 1$: ba cú nhảy là xong. Vì $t \le Q < 2^{18}$ nên chỉ cần 18 tầng.
Bước 2 – DFS một lần, DSU hoàn tác
Danh sách cầu của nút $x$ = các cầu trên đường từ gốc tới $x$. Khi duyệt DFS, đường đi từ gốc tới nút đang đứng chính là một ngăn xếp: đi xuống con thì đẩy thêm một cầu, quay lên thì bỏ cầu cuối. Đó đúng là tình huống của Cách 3! Vậy:
- Vào nút $x$: ghép cầu
(eu[x], ev[x])bằng DSU (không nén đường), ghirec[x]= gốc bị gắn vào (hoặc $-1$ nếu cầu thừa), lưuval[x] = pairs. - Rời nút $x$ (đã duyệt xong mọi con): hoàn tác theo
rec[x].
Cuối cùng đáp án ngày $i$ là val[at[i]]. Mỗi nút được vào/ra đúng một lần, mỗi lần $O(\log N)$.
Một ví dụ có rẽ nhánh: $N = 5$, các thao tác 1 1 2, 1 2 3, 2 1, 1 3 4, 3 2, 1 4 5. Ngày 3 bỏ cầu (2–3), quay về nút 1; ngày 4 thêm (3–4) thành nút 3 — con thứ hai của nút 1; ngày 5 nhảy về nút 2 của ngày 2; ngày 6 thêm (4–5) thành nút 4, con của nút 2.
DFS đi 0 → 1 → 2 → 4 → (hoàn tác 4, hoàn tác 2) → 3 → (hoàn tác 3, hoàn tác 1). Đáp án 6 ngày: 1, 3, 1, 2, 3, 4.
Mô phỏng dưới đây chạy cả hai bước: dựng cây (có nhảy lên tổ tiên), rồi DFS với DSU hoàn tác. Các bạn sửa thao tác tuỳ thích (có thể dùng cả 3 loại).
Code đầy đủ (DFS viết bằng vòng lặp với ngăn xếp: gặp số $x \ge 0$ là "vào nút $x$", gặp ~x (số âm) là "rời nút $x$"; nhờ vậy không sợ tràn ngăn xếp đệ quy khi cây sâu $2 \cdot 10^5$ tầng):
#include <bits/stdc++.h>
using namespace std;
const int MAXQ = 200005, LOG = 18;
int up[LOG][MAXQ], dep[MAXQ], eu[MAXQ], ev[MAXQ];
int head[MAXQ], nxt[MAXQ], rec[MAXQ], at[MAXQ];
int par[MAXQ], sz[MAXQ];
long long val[MAXQ];
int findRoot(int x) {
while (par[x] != x) x = par[x];
return x;
}
int main() {
int n, q;
scanf("%d %d", &n, &q);
int cnt = 1; // nut 0 = phuong an rong
for (int j = 0; j < LOG; j++) up[j][0] = 0;
at[0] = 0;
for (int i = 1; i <= q; i++) {
int type;
scanf("%d", &type);
if (type == 1) {
int u, v;
scanf("%d %d", &u, &v);
int x = cnt++;
eu[x] = u; ev[x] = v;
up[0][x] = at[i - 1];
dep[x] = dep[at[i - 1]] + 1;
for (int j = 1; j < LOG; j++) up[j][x] = up[j - 1][up[j - 1][x]];
at[i] = x;
} else if (type == 2) {
int t;
scanf("%d", &t);
int x = at[i - 1];
for (int j = 0; j < LOG; j++)
if (t >> j & 1) x = up[j][x];
at[i] = x;
} else {
int k;
scanf("%d", &k);
at[i] = at[k];
}
}
// danh sach con cua moi nut trong cay phuong an
for (int x = 0; x < cnt; x++) head[x] = -1;
for (int x = cnt - 1; x >= 1; x--) {
nxt[x] = head[up[0][x]];
head[up[0][x]] = x;
}
for (int i = 1; i <= n; i++) { par[i] = i; sz[i] = 1; }
long long pairs = 0;
vector<int> st;
st.push_back(0);
val[0] = 0;
while (!st.empty()) {
int x = st.back(); st.pop_back();
if (x >= 0) {
if (x > 0) { // di vao nut x: noi cau eu[x]-ev[x]
int a = findRoot(eu[x]), b = findRoot(ev[x]);
if (a == b) rec[x] = -1;
else {
if (sz[a] < sz[b]) swap(a, b);
pairs += (long long)sz[a] * sz[b];
par[b] = a; sz[a] += sz[b];
rec[x] = b;
}
val[x] = pairs;
}
st.push_back(~x); // danh dau luc roi khoi x
for (int c = head[x]; c != -1; c = nxt[c]) st.push_back(c);
} else {
x = ~x; // roi khoi nut x: hoan tac
if (x > 0 && rec[x] != -1) {
int b = rec[x], a = par[b];
sz[a] -= sz[b];
pairs -= (long long)sz[a] * sz[b];
par[b] = b;
}
}
}
string out;
char buf[24];
for (int i = 1; i <= q; i++) {
int len = sprintf(buf, "%lld\n", val[at[i]]);
out.append(buf, len);
}
fputs(out.c_str(), stdout);
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
LOG = 18
par0 = [0] * (q + 1) # cha cua nut trong cay phuong an
dep = [0] * (q + 1)
eu = [0] * (q + 1); ev = [0] * (q + 1)
up = [[0] * (q + 1) for _ in range(LOG)]
at = [0] * (q + 1)
cnt = 1
pos = 2
for i in range(1, q + 1):
typ = data[pos]
if typ == b'1':
x = cnt; cnt += 1
eu[x] = int(data[pos + 1]); ev[x] = int(data[pos + 2]); pos += 3
p = at[i - 1]
par0[x] = p
dep[x] = dep[p] + 1
up[0][x] = p
for j in range(1, LOG):
p = up[j - 1][p]
up[j][x] = p
if p == 0:
break # cac tang cao hon deu bang 0
at[i] = x
elif typ == b'2':
t = int(data[pos + 1]); pos += 2
x = at[i - 1]
j = 0
while t:
if t & 1:
x = up[j][x]
t >>= 1; j += 1
at[i] = x
else:
k = int(data[pos + 1]); pos += 2
at[i] = at[k]
# danh sach con
head = [-1] * cnt
nxt = [-1] * cnt
for x in range(cnt - 1, 0, -1):
p = par0[x]
nxt[x] = head[p]
head[p] = x
par = list(range(n + 1))
sz = [1] * (n + 1)
rec = [-1] * cnt
val = [0] * cnt
pairs = 0
st = [0]
while st:
x = st.pop()
if x >= 0:
if x > 0:
a = eu[x]
while par[a] != a:
a = par[a]
b = ev[x]
while par[b] != b:
b = par[b]
if a != b:
if sz[a] < sz[b]:
a, b = b, a
pairs += sz[a] * sz[b]
par[b] = a
sz[a] += sz[b]
rec[x] = b
val[x] = pairs
st.append(~x)
c = head[x]
while c != -1:
st.append(c)
c = nxt[c]
else:
x = ~x
b = rec[x]
if b != -1:
a = par[b]
sz[a] -= sz[b]
pairs -= sz[a] * sz[b]
par[b] = b
sys.stdout.write('\n'.join([str(val[at[i]]) for i in range(1, q + 1)]) + '\n')
main()find có nén đường. Ở đây nén đường sẽ "đi tắt" qua những gốc mà về sau bị tách ra khi hoàn tác, làm DSU sai. Phải dùng hợp theo kích thước, không nén.Giờ các bạn hãy chạy tay từng dòng code của lời giải trên với dữ liệu nhỏ (N ≤ 8, Q ≤ 10) để thấy rõ cả hai bước.
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Điểm |
|---|---|---|---|---|---|
| Cách 1 – chép danh sách, dựng lại DSU | Đúng | TLE | TLE | TLE | 20 |
| Cách 2 – DSU thường (bỏ qua thao tác 2, 3) | WA | Đúng | WA | WA | 20 |
| Cách 3 – DSU hoàn tác kiểu ngăn xếp | WA | Đúng | Đúng | WA | 45 |
| Cách 4 – cây phương án + nhảy nhị phân + DFS hoàn tác | Đúng | Đúng | Đúng | Đúng | 100 |
Sai: biến đếm cặp kiểu int | Đúng | 2/7 | 3/8 | 2/9 | 42,9 |
| Sai: thao tác 2 leo từng bậc (không nhảy nhị phân) | Đúng | Đúng | Đúng | TLE | 65 |
| Sai: cầu thừa không ghi lịch sử, lúc rời nút vẫn hoàn tác | 5/8 | Đúng | 3/8 | 3/9 | 53,5 |
| Sai: DSU có nén đường đi | Đúng | Đúng | 4/8 | Đúng | 87,5 |
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: 32 test (subtask 1: 8 test, subtask 2: 7 test, subtask 3: 8 test, subtask 4: 9 test), chấm kiểu "đúng test nào được điểm test đó". Lời giải chuẩn chạy tối đa khoảng 0,2 giây; bản Python chạy dưới 2 giây ngay cả trên CPython. Mọi test của subtask 4 đều có đoạn "quay về phương án $10^5$ cầu rồi bỏ rất nhiều cầu" liên tục, nên leo từng bậc chắc chắn quá thời gian. Lỗi nén đường đi khá "lì": nó chỉ lộ ra khi một đỉnh đã được nén trỏ thẳng tới một gốc mà sau đó bị tách ra, nên một số test vẫn lọt — nhưng đừng vì thế mà liều nhé!
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 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét