Xor path (Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng C1, C2)

Nguồn: Tin học trẻ 2025 Độ khó: Khó Đồ thị DSU có trọng số Cơ sở XOR (Gauss) Offline ngược thời gian

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2025 – Vòng khu vực miền Nam – Bảng C1 và Bảng C2 (bài Xor path). Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho đồ thị vô hướng, liên thông, có trọng số gồm $N$ đỉnh và $M$ cạnh (cạnh đánh số $1..M$ theo thứ tự trong dữ liệu vào). Cần xử lý $Q$ truy vấn thuộc một trong hai loại:

• 1 i: xóa cạnh thứ $i$ ($1 \le i \le M$) khỏi đồ thị;
• 2 u v: tìm đường đi từ $u$ tới $v$ có giá trị nhỏ nhất, trong đó giá trị của đường đi là XOR trọng số của mọi cạnh trên đường (được phép đi qua một cạnh nhiều lần, mỗi lần đi qua đều tính vào XOR); hoặc cho biết không có đường đi.

Nhắc lại: XOR (kí hiệu $\oplus$) của hai số không âm $x, y$ là số $z$ mà bit thứ $k$ của $z$ bằng 0 khi bit thứ $k$ của $x$ và $y$ giống nhau, bằng 1 khi khác nhau.

Dữ liệu vào:

• Dòng đầu: ba số nguyên dương $N, M, Q$ ($N, M, Q \le 2 \cdot 10^5$).
• $M$ dòng tiếp: mỗi dòng ba số $u, v, w$ – cạnh nối $u$ và $v$ ($1 \le u, v \le N$) với trọng số $w$ ($0 \le w \le 10^9$).
• $Q$ dòng tiếp: mỗi dòng một truy vấn theo hai dạng trên.

Kết quả: với mỗi truy vấn loại 2, theo thứ tự, in trên một dòng giá trị nhỏ nhất tìm được, hoặc $-1$ nếu không có đường đi từ $u$ tới $v$.

Subtask:

• Subtask 1 (30%): $M = N - 1$;
• Subtask 2 (30%): $M = N$;
• Subtask 3 (30%): $Q = 1$; $N, w \le 1000$;
• Subtask 4 (10%): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây. Dữ liệu nhập từ bàn phím, in ra màn hình.

Ghi chú của mình: đề gốc ghi "cạnh từ $u$ đến $v$" nhưng ví dụ cho thấy đồ thị vô hướng. Đề không nói gì khi một cạnh bị xóa lần thứ hai – cạnh đã xóa thì xóa lại không có tác dụng (bộ test có vài lệnh như vậy). Đồ thị có thể có khuyên (cạnh $u = v$) và nhiều cạnh nối cùng hai đỉnh.

Ví dụ – input

5 5 5
1 2 2
2 3 2
3 4 2
2 5 0
5 3 1
2 1 4
1 4
2 1 4
1 2
2 1 4

Ví dụ – output

1
2
-1

Giải thích: các cạnh: (1) $1–2$ nặng 2, (2) $2–3$ nặng 2, (3) $3–4$ nặng 2, (4) $2–5$ nặng 0, (5) $5–3$ nặng 1.

• Truy vấn 1: đường $1 \to 2 \to 3 \to 4$ có giá trị $2 \oplus 2 \oplus 2 = 2$, nhưng đường $1 \to 2 \to 5 \to 3 \to 4$ có giá trị $2 \oplus 0 \oplus 1 \oplus 2 = 1$ – nhỏ nhất, in 1.
• Xóa cạnh 4 ($2–5$). Truy vấn 2: chỉ còn cách đi $1 \to 2 \to 3 \to 4$ (đi vòng qua 5 rồi quay lại thì các cạnh lặp hai lần triệt tiêu nhau), in 2.
• Xóa cạnh 2 ($2–3$). Đỉnh 1 chỉ còn nối với đỉnh 2, không tới được 4, in $-1$.

Lời mở đầu

Đây là bài khó nhất của đề khu vực miền Nam bảng C, gom ba kiến thức "nâng cao" vào một chỗ: XOR trên chu trình và cơ sở tuyến tính (khử Gauss trên bit), DSU lưu thêm XOR tới gốc, và mẹo đảo ngược thời gian để biến "xóa cạnh" thành "thêm cạnh". Mình đi từ cách tính lại từ đầu cho mỗi truy vấn (ăn subtask 3 và các test nhỏ) tới lời giải đầy đủ.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test20 testÝ tưởngchu trình + cơ sởCách 1tính lại – 30đCách 2ngược thời gian – 100đTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ subtask của đề: 20 test. Ví dụ của đề ($M = N = 5$) là test 7, thuộc subtask 2. Test 13 ($N = M = Q = 1$, một khuyên) thỏa cả subtask 2 lẫn 3.

Test	$N$	$M$	$Q$	$w$ lớn nhất	Khuyên / cạnh lặp	Lệnh xóa (xóa lại)	Truy vấn 2	Số lần in −1
1	10	9	20	14	0 / 0	8 (0)	12	6
2	200.000	199.999	200.000	999.996.520	0 / 0	5.987 (0)	194.013	46.793
3	200.000	199.999	200.000	999.994.295	0 / 0	105 (0)	199.895	176.006
4	200.000	199.999	200.000	999.990.406	0 / 0	60.145 (6119)	139.855	33.537
5	200.000	199.999	200.000	536.870.912	0 / 0	204 (0)	199.796	174.746
6	200.000	199.999	200.000	999.995.550	0 / 0	0 (0)	200.000	0
7	5	5	5	2	0 / 0	2 (0)	3	1
8	8	8	20	7	0 / 0	9 (1)	11	7
9	200.000	200.000	200.000	999.997.781	0 / 0	4.000 (0)	196.000	20.902
10	200.000	200.000	200.000	536.870.912	0 / 0	59 (0)	199.941	146.663
11	200.000	200.000	200.000	1.000.000.000	0 / 0	960 (3)	199.040	183.632
12	200.000	200.000	200.000	999.997.584	0 / 0	80.053 (0)	119.947	98.358
13	1	1	1	7	1 / 0	0 (0)	1	0
14	1.000	1.003	1	999	0 / 0	0 (0)	1	0
15	1.000	999	1	1.000	0 / 0	0 (0)	1	0
16	1.000	200.000	1	1.000	11.046 / 54.936	0 (0)	1	0
17	1.000	1.000	1	1.000	0 / 0	0 (0)	1	0
18	2	200.000	1	1.000	105.270 / 199.997	0 (0)	1	0
19	199.988	200.000	200.000	999.998.565	0 / 0	2.004 (0)	197.996	15.489
20	150.000	200.000	200.000	536.870.912	2.486 / 5.026	6.111 (60)	193.889	1.669

• Các test 4, 8, 11, 20 có lệnh xóa lại một cạnh đã xóa (cột "xóa lại").
• Subtask 3 có test $M = 2 \cdot 10^5$ cạnh trên chỉ $N = 2$ hoặc $1000$ đỉnh – rất nhiều khuyên và cạnh lặp.

Đã nộp thử trên bộ chấm chính thức

Lời giải đầy đủ theo ý tưởng cách 2 mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 tính lại mỗi truy vấn	Cách 2 offline + DSU, C++	Cách 2 Python
Subtask 1 (30%)	$M = N - 1$	1–6	1/6	6/6	2/6
Subtask 2 (30%)	$M = N$	7–12	2/6	6/6	2/6
Subtask 3 (30%)	$Q = 1$; $N, w \le 1000$	13–18	6/6	6/6	6/6
Subtask 4 (10%)	không ràng buộc thêm	19–20	0/2	2/2	0/2

Ý tưởngĐường đi XOR = một đường bất kì ⊕ một tổ hợp các chu trình

Nhận xét 1 – đi qua cạnh hai lần là "không đi". Vì $a \oplus a = 0$, nếu một đường đi qua một cạnh hai lần thì đóng góp của cạnh đó bị triệt tiêu. Do đó:

• Nếu $u$, $v$ ở hai thành phần liên thông khác nhau → in $-1$.
• Từ $u$ ta có thể "đi tới một chu trình bất kì, đi một vòng rồi quay về" – đoạn đi tới và quay về bị triệt tiêu, chỉ còn lại XOR của chu trình. Vậy mọi giá trị đạt được có dạng $$\text{giá trị} = P \oplus c_1 \oplus c_2 \oplus \dots$$ với $P$ là XOR của một đường đi cố định từ $u$ tới $v$, còn $c_1, c_2, \dots$ là XOR của các chu trình trong thành phần.

Nhận xét 2 – chỉ cần các chu trình "cơ bản". Dựng một cây khung (BFS/DFS) và gọi $d[x]$ = XOR đường đi trên cây từ gốc tới $x$. Khi đó $P = d[u] \oplus d[v]$, và mỗi cạnh ngoài cây $(x, y, w)$ cho một chu trình $c = d[x] \oplus d[y] \oplus w$. Mọi chu trình đều là XOR của một số chu trình cơ bản này.

Nhận xét 3 – cơ sở tuyến tính (Gauss trên bit). Tập các giá trị $c_i$ có thể rất lớn ($M - N + 1$ chu trình), nhưng ta chỉ cần giữ tối đa 30 số (vì $w < 2^{30}$): bs[b] là một số có bit cao nhất đúng bằng $b$. Chèn một số $c$: đi từ bit cao xuống, gặp bit 1 ở vị trí $b$ thì nếu bs[b] trống – đặt vào đó, ngược lại $c \mathrel{⊕}= bs[b]$ và đi tiếp. Muốn $P \oplus (\dots)$ nhỏ nhất: đi từ bit cao xuống, nếu bit $b$ của $P$ đang là 1 và có bs[b] thì $P \mathrel{⊕}= bs[b]$ (tắt bit đó đi, các bit cao hơn không bị ảnh hưởng). Tham lam từ bit cao là đúng vì tắt được một bit cao luôn lợi hơn mọi thay đổi ở các bit thấp.

Em nhập đồ thị (mỗi cạnh u v w, cách nhau bởi dấu ;) và hai đỉnh $u, v$ rồi bấm Tiếp: máy BFS từ $u$ dựng cây khung (cạnh xanh) và $d[x]$, mỗi cạnh ngoài cây (cạnh đỏ) cho một chu trình được chèn vào cơ sở, cuối cùng giảm $d[v]$ thành nhỏ nhất:

N = Cạnh u v w (cách nhau bởi ;) = u = v =

Ví dụ nhanh:

Cách 1Tính lại từ đầu cho mỗi truy vấn – $O(Q \cdot (N + M) \cdot 30)$

Áp dụng thẳng 3 nhận xét: với mỗi truy vấn loại 2, BFS từ $u$ trên các cạnh còn sống. Khi đi theo cạnh $(x, y)$: nếu $y$ chưa thăm thì $d[y] = d[x] \oplus w$; nếu đã thăm thì $d[x] \oplus w \oplus d[y]$ là XOR của một chu trình (hoặc bằng 0 với chính cạnh cây đi ngược lại – chèn số 0 không sao) → chèn vào cơ sở. Xóa cạnh chỉ là đánh dấu alive[e] = 0.

C++▶ Chạy tay từng dòng codeCách 1: mỗi truy vấn BFS lại từ u trên các cạnh còn sống, chèn chu trình vào cơ sở rồi giảm d[v].

Dữ liệu vào (stdin) – sửa thoải mái5 5 5 1 2 2 2 3 2 3 4 2 2 5 0 5 3 1 2 1 4 1 4 2 1 4 1 2 2 1 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Khuyên $(x, x, w)$ chỉ được thêm vào danh sách kề một lần; khi BFS gặp nó thì $d[x] \oplus w \oplus d[x] = w$ – đúng là chu trình chỉ gồm khuyên đó.
2. Mỗi cạnh được xét 2 lần (từ hai đầu), mỗi lần chèn tốn tối đa 30 bước, nên mỗi truy vấn $O((N + M) \cdot 30)$.

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

Thời gian$O(Q \cdot (N + M) \cdot 30)$

Kết quả chạy thật: Bản C++ đúng 9/20 test, quá thời gian test 2–6, 9–12, 19–20 (các test đúng chạy lâu nhất 0.096s). Cách này qua trọn subtask 3 ($Q = 1$) và các test nhỏ (test 1, 7, 8), nhưng với $Q = 2 \cdot 10^5$ truy vấn trên đồ thị $2 \cdot 10^5$ cạnh thì hết hy vọng → khoảng 30 điểm.

Cách 2Đảo ngược thời gian + DSU có XOR + gộp cơ sở – full

Khó khăn còn lại là xóa cạnh: xóa thì cây khung bị vỡ, chu trình mất đi... rất khó cập nhật. Mẹo kinh điển: đọc hết các truy vấn trước (xử lý offline) rồi đi ngược thời gian từ truy vấn cuối về truy vấn đầu. Đi ngược thì "xóa cạnh" trở thành "thêm cạnh" – mà thêm cạnh thì DSU làm rất giỏi:

1. Với mỗi cạnh, ghi lại thời điểm nó bị xóa lần đầu (firstDel; các lần xóa sau không có tác dụng). Cạnh không bao giờ bị xóa thì có mặt từ đầu tới cuối → thêm vào DSU trước tiên.
2. Duyệt $i = Q-1 \to 0$: gặp lệnh xóa đúng lần đầu của cạnh $e$ thì thêm cạnh $e$ (vì trước thời điểm $i$, cạnh $e$ còn tồn tại); gặp truy vấn loại 2 thì trả lời ngay với đồ thị hiện tại, lưu vào ans[i].
3. In các đáp án theo đúng thứ tự ban đầu.

DSU có XOR: ngoài par[x], lưu thêm px[x] = XOR của "cạnh ảo" từ $x$ tới cha. Hàm findRoot(u) nén đường đi và sau đó px[u] chính là XOR từ $u$ tới gốc – đóng vai trò $d[u]$ của cây khung. Gốc của mỗi thành phần giữ cơ sở chu trình bs[gốc]. Thêm cạnh $(u, v, w)$:

• Cùng thành phần: tạo thêm chu trình $px[u] \oplus px[v] \oplus w$ → chèn vào cơ sở của gốc.
• Khác thành phần: nối gốc $r_v$ vào gốc $r_u$ với $px[r_v]$ $= px[u] \oplus px[v] \oplus w$ (để đường $u \to v$ qua cạnh mới khớp XOR), rồi chèn tối đa 30 vector của cơ sở $r_v$ vào cơ sở $r_u$. Luôn gộp thành phần nhỏ vào lớn.

Trả lời truy vấn: khác gốc → $-1$; cùng gốc → giảm $px[u] \oplus px[v]$ bằng cơ sở của gốc.

C++▶ Chạy tay từng dòng codeCách 2: đọc hết truy vấn, đi ngược thời gian; xóa cạnh thành thêm cạnh vào DSU có XOR và cơ sở chu trình.

Dữ liệu vào (stdin) – sửa thoải mái5 5 5 1 2 2 2 3 2 3 4 2 2 5 0 5 3 1 2 1 4 1 4 2 1 4 1 2 2 1 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Trong findRoot: gọi đệ quy cho cha p trước, lúc đó px[p] đã là XOR từ p tới gốc, nên px[u] ^= px[p] cho XOR từ $u$ tới gốc. Gốc luôn có px = 0. Nhờ gộp nhỏ vào lớn, cây DSU cao tối đa $\log N$ nên đệ quy không sâu.
2. Mỗi lần gộp tốn $30 \cdot 30$ phép tính cho cơ sở, có tối đa $N - 1$ lần gộp → khoảng $1{,}8 \cdot 10^8$ phép tính đơn giản trong trường hợp xấu nhất, thực tế ít hơn nhiều (cơ sở thường gần rỗng).
3. Đề không nói gì về xóa lặp; nếu coi lần xóa thứ hai cũng là "thêm cạnh" khi đi ngược thì cạnh bị thêm hai lần, tạo chu trình giả $w \oplus w = 0$ – may là vô hại, nhưng thêm cạnh vào quá sớm (ở lần xóa sau) thì sai. Vì vậy chỉ thêm ở lần xóa đầu tiên.

Không gian$O(N \cdot 30 + M + Q)$

Thời gian$O((M + Q) \log N + N \cdot 30^2)$

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.163s. Full điểm. Bản Python đúng 10/20 test, quá thời gian test 2–3, 5–6, 9–12, 19–20 (các test đúng chạy lâu nhất 0.889s) – Python không đủ nhanh cho $2 \cdot 10^5$ thao tác DSU kèm cơ sở trong 1 giây.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
1. BFS + cơ sở XOR cho mỗi truy vấn	C++	9/20	0.096s	30%
2. Đảo ngược thời gian + DSU có XOR + cơ sở	C++	20/20	0.163s	100%
	Python	10/20	0.889s	30%

Ghi chú của mình: thời gian là thời gian CPU đo trên máy mình (giới hạn 1 giây). Ba "món" đáng nhớ: (1) bài XOR đường đi được lặp cạnh → XOR một đường bất kì + cơ sở các chu trình; (2) cơ sở tuyến tính 30 số để tìm XOR nhỏ nhất/lớn nhất; (3) chỉ có xóa mà không có thêm → đảo ngược thời gian để dùng DSU.

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 😇