Robot (Tin học trẻ toàn quốc 2024 – Vòng khu vực – Bảng C1, C2)
Đề bài
Cho hai đơn đồ thị vô hướng, liên thông $G_1$ và $G_2$, cùng có $n$ đỉnh đánh số từ $1$ đến $n$ (hai đồ thị có cùng tập đỉnh nhưng tập cạnh khác nhau).
Với hai đỉnh $s$ và $t$: đặt robot thứ nhất tại đỉnh $s$ của $G_1$, robot thứ hai cũng tại đỉnh $s$ nhưng trên $G_2$. Ta cần đưa cả hai robot về đỉnh $t$ theo luật: ở mỗi đơn vị thời gian, ta chọn một đỉnh $v$; sau đó mỗi robot, nếu trong đồ thị của nó có cạnh nối vị trí hiện tại với $v$, thì được chọn đi tới $v$ hoặc đứng yên (không có cạnh thì phải đứng yên).
Gọi $d(s, t)$ là thời gian ít nhất để cả hai robot cùng có mặt tại đỉnh $t$ ($d(s, s) = 0$).
Yêu cầu: tính tổng $d(s, t)$ trên tất cả các cặp đỉnh $(s, t)$.
Dữ liệu vào:
- Dòng đầu: số nguyên dương $n$ ($n \le 500$).
- Dòng tiếp theo: số cạnh $m_1$ của $G_1$; $m_1$ dòng sau, mỗi dòng hai số $x_i, y_i$ – một cạnh của $G_1$.
- Dòng tiếp theo: số cạnh $m_2$ của $G_2$; $m_2$ dòng sau, mỗi dòng hai số $u_j, v_j$ – một cạnh của $G_2$.
Kết quả: một số nguyên là tổng các giá trị $d(s, t)$ với mọi cặp $(s, t)$.
Subtask:
- Subtask 1 (50%): $n \le 100$;
- Subtask 2 (50%): $n \le 500$.
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.
3
3
1 2
2 3
3 1
2
1 2
2 38Giải thích: $G_1$ là tam giác $1-2-3$, $G_2$ là đường đi $1 - 2 - 3$. Các cặp kề nhau trong cả hai đồ thị có $d = 1$: $d(1,2)$ $= d(2,1)$ $= d(2,3)$ $= d(3,2)$ $= 1$. Với $(s, t) = (1, 3)$: bước 1 chọn $v = 2$ (robot thứ hai đi tới 2, robot thứ nhất đứng yên), bước 2 chọn $v = 3$ (cả hai cùng đi tới 3) nên $d(1, 3) = 2$; tương tự $d(3, 1) = 2$. Tổng $4 \cdot 1 + 2 \cdot 2 = 8$.
long long cho chắc.Lời mở đầu
Bài đồ thị hay của Bảng C1/C2: hai robot đi "đồng bộ" theo cùng một đỉnh được chọn. Cách tự nhiên là BFS trên cặp vị trí $(a, b)$ – đúng nhưng chỉ đủ cho $n \le 100$. Mấu chốt để full điểm là một nhận xét: giữa hai lần hai robot gặp nhau, chi phí chỉ phụ thuộc khoảng cách trong từng đồ thị. Khi đó bài toán trở về đường đi ngắn nhất trên một đồ thị đầy đủ $n$ đỉnh – dùng Floyd.
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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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, mỗi subtask 10 test (test 1 là ví dụ của đề).
| Nhóm | Test | $n$ lớn nhất | $m_1$ lớn nhất | $m_2$ lớn nhất | Có đồ thị là cây ($m = n - 1$) | Có đồ thị đầy đủ | Đáp án lớn nhất |
|---|---|---|---|---|---|---|---|
| Subtask 1 | 1–10 | 100 | 4.950 | 4.950 | test 1–4, 6 | test 1–2, 6, 10 | 617.810 |
| Subtask 2 | 11–20 | 500 | 124.750 | 124.750 | test 11–13, 18 | test 18–19 | 80.458.498 |
- Có các cặp đồ thị "khó chịu": hai đường đi với thứ tự đỉnh khác nhau (đáp án lớn nhất), đường đi với hình sao, một đồ thị và phần bù của nó (hai robot không bao giờ đi chung được một cạnh), hai đồ thị giống hệt nhau.
- Test 19 là hai đồ thị đầy đủ $n = 500$ – mỗi đồ thị $124\,750$ cạnh, khi đó mọi $d(s, t) = 1$. Dữ liệu vào gần 2 MB nên nhớ
ios::sync_with_stdio(0).
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 BFS trạng thái C++ | Cách 2 BFS + Floyd C++ | Cách 2 Python |
|---|---|---|---|---|---|
| Subtask 1 (50%) | $n \le 100$ | 1–10 | 10/10 | 10/10 | 10/10 |
| Subtask 2 (50%) | $n \le 500$ | 11–20 | 0/10 | 10/10 | 0/10 |
Ý tưởngTrạng thái là cặp vị trí, và các "lần gặp nhau"
Trạng thái của bài là cặp $(a, b)$: robot 1 ở đỉnh $a$ (trong $G_1$), robot 2 ở đỉnh $b$ (trong $G_2$). Chọn một đỉnh $v$ chỉ có ba kiểu thay đổi có ích:
- $v$ kề $a$ trong $G_1$: robot 1 sang $v$, robot 2 đứng yên → $(v, b)$;
- $v$ kề $b$ trong $G_2$: robot 2 sang $v$, robot 1 đứng yên → $(a, v)$;
- $v$ kề $a$ trong $G_1$ và kề $b$ trong $G_2$: cả hai cùng sang $v$ → $(v, v)$.
Vì cả hai robot chỉ đi tới cùng một đỉnh $v$, bước nào hai robot cùng di chuyển thì sau bước đó chúng đứng chung một đỉnh. Ta gọi trạng thái $(w, w)$ là một lần gặp nhau. Hành trình từ $(s, s)$ tới $(t, t)$ được cắt thành nhiều đoạn, mỗi đoạn đi từ một lần gặp $(u, u)$ tới lần gặp kế tiếp $(w, w)$.
- Không thể ít hơn: trong đoạn, hai robot không gặp nhau ở giữa, nên mọi bước (trừ bước cuối) chỉ có một robot di chuyển. Robot 1 cần ít nhất $D_1$ lần di chuyển, robot 2 cần ít nhất $D_2$ lần, và chỉ bước cuối mới có thể "gộp" hai lần di chuyển → ít nhất $D_1 + D_2 - 1$ bước.
- Làm được: cho robot 1 tự đi theo đường ngắn nhất tới đỉnh kề $w$ ($D_1 - 1$ bước), robot 2 cũng vậy ($D_2 - 1$ bước), rồi một bước chọn $v = w$ cho cả hai cùng nhảy vào $w$.
Vậy đặt $c(u, w)$ $= D_1(u, w) + D_2(u, w) - 1$ (và $c(u, u) = 0$). Hành trình ngắn nhất là một dãy lần gặp $s = u_0, u_1, \dots, u_k = t$, nên $d(s, t)$ chính là đường đi ngắn nhất từ $s$ tới $t$ trên đồ thị đầy đủ với trọng số $c$. Ví dụ đề: $c(1, 3)$ $= D_1 + D_2 - 1$ $= 1 + 2 - 1$ $= 2$ ✓.
Em nhập hai đồ thị, chọn $s$, $t$ rồi bấm Tiếp để xem một hành trình ngắn nhất (tìm bằng BFS trên cặp vị trí): chấm đỏ là robot 1 trên $G_1$, chấm xanh là robot 2 trên $G_2$, viền cam là đỉnh $v$ được chọn. Bước cuối tách hành trình thành các đoạn và so với công thức $D_1 + D_2 - 1$:
Cách 1BFS trên cặp vị trí (Subtask 1)
Với mỗi $s$, chạy BFS trên $n^2$ trạng thái $(a, b)$ xuất phát từ $(s, s)$, theo đúng ba kiểu chuyển ở trên. Khi BFS xong, $d(s, t)$ = d[t][t]. Để kiểm tra nhanh "$v$ có kề $b$ trong $G_2$ không" mình dùng thêm ma trận kề e2.
- Không cần xét "đứng yên cả hai" vì nó không làm thay đổi trạng thái.
- Kiểu thứ ba (cả hai cùng đi) chỉ cần duyệt $v$ kề $a$ rồi tra
e2[b][v]– $O(1)$ mỗi lần. - Mỗi lần BFS duyệt $n^2$ trạng thái, mỗi trạng thái $(a, b)$ duyệt $\deg_1(a) + \deg_2(b)$ đỉnh kề, tổng cộng $O(n(m_1 + m_2))$ cho một nguồn $s$.
Kết quả chạy thật: Bản C++ đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.445s). Với $n = 500$, mỗi nguồn có $250\,000$ trạng thái, đồ thị dày thì mỗi trạng thái duyệt hàng trăm đỉnh kề – nhân thêm 500 nguồn là quá xa giới hạn. Được 50 điểm.
Cách 2Tách đoạn gặp nhau + Floyd – O(n³) (full)
Ba bước:
- BFS từ mọi đỉnh trong $G_1$ và trong $G_2$ để có $D_1$, $D_2$ – mỗi đồ thị $O(n(n + m))$.
- Lập ma trận $c(u, w)$ $= D_1(u, w) + D_2(u, w) - 1$ với $u \ne w$, $c(u, u) = 0$.
- Chạy Floyd trên ma trận $c$ (ghép nhiều đoạn lại), rồi cộng tất cả $c(i, j)$.
- Vì $G_1$, $G_2$ liên thông nên mọi $D \ge 1$ khi $u \ne w$, $c(u, w) \ge 1$, không có giá trị $-1$ lọt vào.
- Vì sao cần Floyd? Có khi gặp nhau ở các đỉnh trung gian lại rẻ hơn đi thẳng một đoạn. Ví dụ đơn giản nhất: $G_1$ và $G_2$ cùng là đường $1-2-3-4$. Đi thẳng một đoạn $1 \to 4$ tốn $c(1, 4) = 3 + 3 - 1 = 5$, nhưng cho hai robot đi cùng nhau (gặp nhau ở 2, ở 3) chỉ tốn $1 + 1 + 1 = 3$. Em thử ví dụ "Đi cùng nhau" trong widget ở trên để thấy.
- Giá trị $c$ nhỏ (không quá $2n$), tổng các $c$ tới cỡ $8 \cdot 10^7$ nên mảng
cdùngint, biếntotaldùnglong long. Lấyc[i][k]ra biếnciktrước vòng $j$ giúp vòng trong chạy nhanh hơn.
Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.344s (phần lớn thời gian là đọc gần 2 MB dữ liệu và Floyd $1{,}25 \cdot 10^8$ phép so sánh). Full điểm.
Bản Python đúng 10/20 test, quá thời gian test 11–20 (các test đúng chạy lâu nhất 0.143s): Floyd $n^3 = 1{,}25 \cdot 10^8$ phép tính là quá sức Python, nên bản Python chỉ được Subtask 1 (50 điểm).
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 trên cặp vị trí, từ mọi $s$ | C++ | 10/20 | 0.445s | 50% |
| 2. Tách đoạn gặp nhau + Floyd $O(n^3)$ | C++ | 20/20 | 0.344s | 100% |
| Python | 10/20 | 0.143s | 50% |
bitset và đọc nhanh bằng fread, nhưng bản cách 2 ở trên (BFS thường) cũng đã đủ nhanh.
Nhận xét
Đăng nhận xét