Hội Chợ

Nguồn: Codeforces Group Độ khó: Khó Đồ thị BFS đa nguồn Xử lý offline

Đề bài

Thắng tham gia thử thách "check-in" trong hội chợ tết của thành phố. Hội chợ gồm có $N$ điểm bán hàng được đánh số từ $1$ đến $N$. Các điểm bán hàng được nối với nhau bởi $M$ đường hai chiều, mỗi đường có một cửa chắn với mã khóa là một số nguyên dương. Các mã khoá trên cửa chắn là đôi một khác nhau. Có $K$ điểm bán hàng đặc biệt $S_1, S_2, \ldots, S_K$ là điểm "check-in" để hoàn thành thử thách.

Ở mỗi lượt, ban đầu cửa chắn tại tất cả các con đường đều khóa. Người chơi sẽ nhận được thông tin gồm hai số tự nhiên $X$ và $D$ tương ứng là số hiệu của điểm bán hàng xuất phát và chìa khóa có số $D$. Chìa khóa có số $D$ sẽ mở được những cánh cửa có mã khóa là bội của $D$. Ví dụ: chìa khoá có số $2$ sẽ mở được các cánh cửa bị khóa bởi mã khoá là $2, 4, 6, 8, \ldots$; chìa có số $7$ sẽ mở được các cửa bị khóa bởi mã khoá là $7, 14, 21, 28, \ldots$ Người chơi cần tìm đường đi như sau:

Xuất phát từ điểm bán hàng $X$;
Đích đến là một trong các điểm bán hàng đặc biệt $S_1, S_2, \ldots, S_K$;
Số lượng con đường đi qua là nhỏ nhất.

Yêu cầu: Thắng tham gia $Q$ lượt chơi, với mỗi lượt Thắng nhận được một cặp số $(X, D)$. Em hãy lập trình đưa ra số lượng con đường nhỏ nhất Thắng cần đi qua để đến đích tại mỗi lượt chơi.

Dữ liệu vào:

Dòng đầu tiên gồm bốn số nguyên dương $N, M, K, Q$ $(N, M, Q \le 3 \times 10^5,\ 1 \le K \le N)$ tương ứng lần lượt là số lượng điểm bán hàng, số lượng con đường nối giữa $N$ điểm bán, số lượng điểm bán đặc biệt và số lượt chơi.
Dòng thứ hai gồm $K$ số nguyên dương $S_1, S_2, \ldots, S_K$ $(1 \le S_i \le N,\ 1 \le i \le K)$ mô tả các điểm bán hàng đặc biệt.
$M$ dòng sau, mỗi dòng gồm ba số nguyên $u, v, c$ $(1 \le u, v \le N,\ 1 \le c \le 10^6)$ mô tả có một đường hai chiều nối giữa điểm bán $u$ và điểm bán $v$ mà trên đường đó có một cánh cửa chắn với mã khóa là $c$.
$Q$ dòng sau, mỗi dòng gồm hai số nguyên $X$ và $D$ là thông tin của mỗi lượt chơi.

Dữ liệu ra: Gồm $Q$ dòng, tương ứng với $Q$ lượt chơi, nếu có đường đi thỏa mãn yêu cầu đề bài thì in ra số con đường nhỏ nhất Thắng cần đi qua để đến đích, ngược lại, nếu không có cách nào để đi đến đích thì in ra $-1$.

Ràng buộc:

Có 30% số test ứng với 30% số điểm có $Q = 1;\ D = 1$;
15% số test khác ứng với 15% số điểm có $K = 1;\ D \le 10$;
25% số test khác ứng với 25% số điểm có $D \le 10$;
20% số test khác ứng với 20% số điểm có $D \le 10^4$;
10% số test còn lại ứng với 10% số điểm không có ràng buộc gì thêm.

Ví dụ – input

Ví dụ – output

Giải thích ví dụ: hội chợ trong ví dụ có 5 điểm bán hàng, 7 con đường, 2 điểm "check-in" là $4$ và $5$:

Đồ thị của ví dụ: số trên mỗi cạnh là mã khóa cửa chắn, điểm 4 và 5 (viền đôi xanh) là các điểm "check-in".

Ở lượt chơi 1, có thể chọn đường đi: $1 \to 3 \to 5$ hoặc $1 \to 3 \to 4$ đều có số lượng con đường đi qua nhỏ nhất là $2$;
Ở lượt chơi 2, không có đường đi thoả mãn;
Ở lượt chơi 3, có thể chọn đường đi: $1 \to 4$;
Ở lượt chơi 4, có thể chọn đường đi: $2 \to 1 \to 3 \to 5$.

Lượt 1: X = 1, D = 2 → mở được các cửa 14, 16, 8, 4. Đi 1 → 3 → 5 (hoặc 1 → 3 → 4), 2 con đường.

Lượt 2: X = 1, D = 5 → chỉ mở được cửa 5 (giữa 2 và 4), điểm 1 bị cô lập → −1.

Lượt 3: X = 1, D = 1 → mở được mọi cửa. Đi thẳng 1 → 4, 1 con đường.

Lượt 4: X = 2, D = 4 → mở được các cửa 16, 8, 4. Đi 2 → 1 → 3 → 5, 3 con đường.

điểm xuất phát Xđường đi ngắn nhấtcửa mở được (mã khóa là bội của D)cửa vẫn khóa

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bài khá dài vì mình đi lần lượt từng subtask, từ cách đơn giản nhất (BFS 1 nguồn) tới cách ăn trọn điểm (BFS đa nguồn + xử lý truy vấn offline), các bạn cứ đọc từ từ nhé.

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

Dành cho tất cả mọi ngườiNộp bài trên Codeforces

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é. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.

Nộp bài trên Codeforces

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

Sub 1BFS 1 nguồn Sub 2BFS ngược Sub 3BFS đa nguồn 100%Offline theo D

Subtask 1Q = 1, D = 1: BFS từ đỉnh xuất phát

Nhận thấy nếu $D = 1$ thì đồ thị cần xét sẽ là đồ thị gốc do mọi số đều chia hết cho $1$ (chìa số 1 mở được mọi cửa). Cùng với đó, $Q = 1$, nên ta chỉ cần xét duy nhất một đỉnh bắt đầu $u = X$.

Bài toán bây giờ chuyển về là bài toán BFS tìm đường đi ngắn nhất bắt đầu từ đỉnh $u$ đến các đỉnh trên đồ thị ban đầu (mỗi con đường tính là 1 bước nên đồ thị coi như không trọng số, BFS cho ngay đường đi ngắn nhất). Sau đó, kết quả của truy vấn sẽ là min đường đi ngắn nhất từ $u$ đến các đỉnh đặc biệt. Nếu min này vẫn là $\infty$ (không đỉnh đặc biệt nào tới được) thì in $-1$.

Mẹo nhỏ trong code

Vì các mã khóa đôi một khác nhau và $\le 10^6$, mình lưu cạnh vào mảng edges[c] = {u, v} với chỉ số chính là mã khóa. Ô nào edges[c].first == 0 nghĩa là không có cạnh mã khóa $c$. Cách lưu này sẽ cực kỳ có ích ở subtask cuối, khi ta cần duyệt nhanh các cạnh có mã khóa là bội của $D$: chỉ cần nhảy $c = D, 2D, 3D, \ldots$

Độ phức tạp: $O(N + M)$ cho BFS (cộng thêm $10^6$ lần duyệt mảng edges để dựng danh sách kề).

Code Subtask 1 – BFS từ X trên đồ thị gốc

#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
bool special[300005];
int ans[300005];
pair<int, int> edges[1000005];
int deg[300005];
pair<int, pair<int, int>> ask[300005];
namespace sub1 {
vector<vector<int>> ad(300005);
int dis[300005];
void solve(){
    queue<int> we;
    we.push(ask[1].second.first);
    for(int i = 1; i <= 1000000; i++){
        if(edges[i].first != 0){
            ad[edges[i].first].push_back(edges[i].second);
            ad[edges[i].second].push_back(edges[i].first);
        }
    }
    for(int i = 1; i <= n; i++)
        dis[i] = 1e9;
    dis[ask[1].second.first] = 0;
    while(!we.empty()){
        int u = we.front();
        we.pop();
        for(auto v : ad[u]){
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                we.push(v);
            }
        }
    }
    int mn = 1e9;
    for(int i = 1; i <= n; i++){
        if(special[i])
            mn = min(mn, dis[i]);
    }
    if(mn > m)
        ans[1] = -1;
    else
        ans[1] = mn;
}
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> q;
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        special[x] = 1;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges[w] = {u, v};
    }
    for(int i = 1; i <= q; i++){
        int x, d;
        cin >> x >> d;
        ask[i] = {d, {x, i}};
    }
    sub1::solve();
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    return 0;
}

import sys
from collections import deque
def main():
    data = sys.stdin.buffer.read().split()
    n, m, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    p = 4
    special = [False] * (n + 1)
    for i in range(k):
        special[int(data[p + i])] = True
    p += k
    ad = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v = int(data[p]), int(data[p + 1])
        p += 3
        ad[u].append(v)
        ad[v].append(u)
    x = int(data[p])                      # Q = 1, D = 1: chỉ 1 truy vấn trên đồ thị gốc
    INF = 10 ** 9
    dis = [INF] * (n + 1)
    dis[x] = 0
    we = deque([x])
    while we:
        u = we.popleft()
        for v in ad[u]:
            if dis[v] > dis[u] + 1:
                dis[v] = dis[u] + 1
                we.append(v)
    mn = min(dis[i] for i in range(1, n + 1) if special[i])
    print(-1 if mn > m else mn)
main()

C++▶ Chạy tay từng dòng codeSubtask 1: BFS từ X trên đồ thị gốc, lấy min khoảng cách tới các điểm đặc biệt.

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;

3int n, m, k, q;

4bool special[300005];

5int ans[300005];

6pair<int, int> edges[1000005];

7int deg[300005];

8pair<int, pair<int, int>> ask[300005];

9namespace sub1 {

10vector<vector<int>> ad(300005);

11int dis[300005];

12void solve(){

13 queue<int> we;

14 we.push(ask[1].second.first);

15 for(int i = 1; i <= 1000000; i++){

16 if(edges[i].first != 0){

17 ad[edges[i].first].push_back(edges[i].second);

18 ad[edges[i].second].push_back(edges[i].first);

19 }

20 }

21 for(int i = 1; i <= n; i++)

22 dis[i] = 1e9;

23 dis[ask[1].second.first] = 0;

24 while(!we.empty()){

25 int u = we.front();

26 we.pop();

27 for(auto v : ad[u]){

28 if(dis[v] > dis[u] + 1){

29 dis[v] = dis[u] + 1;

30 we.push(v);

31 }

32 }

33 }

34 int mn = 1e9;

35 for(int i = 1; i <= n; i++){

36 if(special[i])

37 mn = min(mn, dis[i]);

38 }

39 if(mn > m)

40 ans[1] = -1;

41 else

42 ans[1] = mn;

43}

44};

45int main(){

46 ios::sync_with_stdio(0);

47 cin.tie(0);

48 cin >> n >> m >> k >> q;

49 for(int i = 1; i <= k; i++){

50 int x;

51 cin >> x;

52 special[x] = 1;

53 }

54 for(int i = 1; i <= m; i++){

55 int u, v, w;

56 cin >> u >> v >> w;

57 edges[w] = {u, v};

58 }

59 for(int i = 1; i <= q; i++){

60 int x, d;

61 cin >> x >> d;

62 ask[i] = {d, {x, i}};

63 }

64 sub1::solve();

65 for(int i = 1; i <= q; i++)

66 cout << ans[i] << '\n';

67 return 0;

68}

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

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

Subtask 2K = 1, D ≤ 10: BFS ngược từ điểm đặc biệt

$K = 1$ nên đối với mỗi truy vấn, chúng ta chỉ cần xem xét các đường đi của đỉnh $u$ đến $spe$ (đỉnh đặc biệt duy nhất) trên đồ thị có các cạnh là bội của $D$. Nhưng giờ $Q$ có thể lên tới $3 \times 10^5$, mỗi truy vấn mà BFS lại một lần thì $O(Q \cdot (N + M))$ quá lớn.

Vì $D$ rất nhỏ ($D \le 10$) nên chúng ta có thể xử lý phần này trước khi thực hiện xử lý truy vấn. Ta gọi $dis(i, j)$ là khoảng cách từ $j$ đến đỉnh đặc biệt khi xét đồ thị có các cạnh là bội của $i$. Sau đó, ta sẽ duyệt $i$ từ $1$ đến $10$ để xem xét từng đồ thị có thể xảy ra trong truy vấn.

Lật ngược chiều BFS

Dễ dàng thấy được đường đi ngắn nhất từ $u$ đến $spe$ cũng là đường đi ngắn nhất từ $spe$ đến $u$ vì đây là đồ thị vô hướng. Khi này, đối với mỗi dạng đồ thị có thể, ta sẽ thực hiện BFS từ $spe$ và tính toán hàm $dis(i, j)$ với mọi $j$ trong đồ thị. Mỗi truy vấn $(X, D)$ chỉ việc tra bảng $dis(D, X)$ trong $O(1)$.

Độ phức tạp: $O(10 \cdot (N + M))$ tiền xử lý + $O(1)$ mỗi truy vấn.

Code Subtask 2 – BFS từ điểm đặc biệt cho mỗi D ≤ 10

#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
bool special[300005];
int ans[300005];
pair<int, int> edges[1000005];
int deg[300005];
pair<int, pair<int, int>> ask[300005];
namespace sub2 {
int dis[15][300005];
vector<vector<pair<int, int>>> ad(300005);
void solve(){
    int pos;
    for(int i = 1; i <= n; i++)
        if(special[i])
            pos = i;
    for(int i = 1; i <= 1000000; i++){
        if(edges[i].first != 0){
            ad[edges[i].first].push_back({edges[i].second, i});
            ad[edges[i].second].push_back({edges[i].first, i});
        }
    }
    for(int i = 1; i <= 10; i++){
        for(int j = 1; j <= n; j++)
            dis[i][j] = 1e9;
        queue<int> we;
        we.push(pos);
        dis[i][pos] = 0;
        while(!we.empty()){
            int u = we.front();
            we.pop();
            for(auto v : ad[u]){
                if(v.second % i)
                    continue;
                if(dis[i][v.first] > dis[i][u] + 1){
                    dis[i][v.first] = dis[i][u] + 1;
                    we.push(v.first);
                }
            }
        }
    }
    for(int i = 1; i <= q; i++){
        ans[i] = dis[ask[i].first][ask[i].second.first];
        if(ans[i] > m)
            ans[i] = -1;
    }
}
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> q;
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        special[x] = 1;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges[w] = {u, v};
    }
    for(int i = 1; i <= q; i++){
        int x, d;
        cin >> x >> d;
        ask[i] = {d, {x, i}};
    }
    sub2::solve();
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    return 0;
}

import sys
from collections import deque
def main():
    data = sys.stdin.buffer.read().split()
    n, m, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    p = 4
    pos = int(data[p])                    # K = 1: chỉ có 1 điểm đặc biệt
    p += k
    ad = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, c = int(data[p]), int(data[p + 1]), int(data[p + 2])
        p += 3
        ad[u].append((v, c))
        ad[v].append((u, c))
    INF = 10 ** 9
    dis = [None] * 11
    for i in range(1, 11):                # BFS từ điểm đặc biệt trên đồ thị cạnh là bội của i
        d = [INF] * (n + 1)
        d[pos] = 0
        we = deque([pos])
        while we:
            u = we.popleft()
            for v, c in ad[u]:
                if c % i:
                    continue
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    we.append(v)
        dis[i] = d
    out = []
    for _ in range(q):
        x, D = int(data[p]), int(data[p + 1])
        p += 2
        r = dis[D][x]
        out.append(-1 if r > m else r)
    print('\n'.join(map(str, out)))
main()

C++▶ Chạy tay từng dòng codeSubtask 2: BFS ngược từ điểm đặc biệt duy nhất cho từng i = 1..10, rồi tra bảng.

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;

3int n, m, k, q;

4bool special[300005];

5int ans[300005];

6pair<int, int> edges[1000005];

7int deg[300005];

8pair<int, pair<int, int>> ask[300005];

9namespace sub2 {

10int dis[15][300005];

11vector<vector<pair<int, int>>> ad(300005);

12void solve(){

13 int pos;

14 for(int i = 1; i <= n; i++)

15 if(special[i])

16 pos = i;

17 for(int i = 1; i <= 1000000; i++){

18 if(edges[i].first != 0){

19 ad[edges[i].first].push_back({edges[i].second, i});

20 ad[edges[i].second].push_back({edges[i].first, i});

21 }

22 }

23 for(int i = 1; i <= 10; i++){

24 for(int j = 1; j <= n; j++)

25 dis[i][j] = 1e9;

26 queue<int> we;

27 we.push(pos);

28 dis[i][pos] = 0;

29 while(!we.empty()){

30 int u = we.front();

31 we.pop();

32 for(auto v : ad[u]){

33 if(v.second % i)

34 continue;

35 if(dis[i][v.first] > dis[i][u] + 1){

36 dis[i][v.first] = dis[i][u] + 1;

37 we.push(v.first);

38 }

39 }

40 }

41 }

42 for(int i = 1; i <= q; i++){

43 ans[i] = dis[ask[i].first][ask[i].second.first];

44 if(ans[i] > m)

45 ans[i] = -1;

46 }

47}

48};

49int main(){

50 ios::sync_with_stdio(0);

51 cin.tie(0);

52 cin >> n >> m >> k >> q;

53 for(int i = 1; i <= k; i++){

54 int x;

55 cin >> x;

56 special[x] = 1;

57 }

58 for(int i = 1; i <= m; i++){

59 int u, v, w;

60 cin >> u >> v >> w;

61 edges[w] = {u, v};

62 }

63 for(int i = 1; i <= q; i++){

64 int x, d;

65 cin >> x >> d;

66 ask[i] = {d, {x, i}};

67 }

68 sub2::solve();

69 for(int i = 1; i <= q; i++)

70 cout << ans[i] << '\n';

71 return 0;

72}

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

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

Subtask 3D ≤ 10: BFS đa nguồn (multi-source BFS)

Khi $K$ không bằng 1, ta vẫn giữ nguyên ý tưởng tương tự subtask 2, nhưng thay vì chọn điểm để BFS là duy nhất một điểm đặc biệt thì ta sẽ chọn tất cả các điểm đặc biệt để thực hiện BFS đồng thời cùng một lúc: ban đầu đẩy hết $K$ điểm đặc biệt vào hàng đợi với khoảng cách $0$, rồi BFS lan ra như bình thường.

Vì sao BFS đa nguồn đúng? Hãy tưởng tượng thêm 1 đỉnh ảo $S^*$ nối tới tất cả $K$ điểm đặc biệt. Khoảng cách từ $X$ đến điểm đặc biệt gần nhất chính bằng khoảng cách từ $X$ đến $S^*$ trừ đi $1$. BFS từ $S^*$ thì bước đầu tiên đẩy đúng $K$ điểm đặc biệt vào hàng đợi với khoảng cách (đã trừ 1) bằng $0$, chính là điều code đang làm. Vì thế $dis(i, j)$ lúc này là khoảng cách từ $j$ tới điểm đặc biệt gần nhất.

Độ phức tạp: $O(10 \cdot (N + M))$.

Code Subtask 3 – BFS đa nguồn cho mỗi D ≤ 10

#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
bool special[300005];
int ans[300005];
pair<int, int> edges[1000005];
int deg[300005];
pair<int, pair<int, int>> ask[300005];
namespace sub3 {
int dis[15][300005];
vector<vector<pair<int, int>>> ad(300005);
void solve(){
    for(int i = 1; i <= 1000000; i++){
        if(edges[i].first != 0){
            ad[edges[i].first].push_back({edges[i].second, i});
            ad[edges[i].second].push_back({edges[i].first, i});
        }
    }
    for(int i = 1; i <= 10; i++){
        queue<int> we;
        for(int j = 1; j <= n; j++)
            dis[i][j] = 1e9;
        for(int j = 1; j <= n; j++)
            if(special[j]){
                we.push(j);
                dis[i][j] = 0;
            }
        while(!we.empty()){
            int u = we.front();
            we.pop();
            for(auto v : ad[u]){
                if(v.second % i)
                    continue;
                if(dis[i][v.first] > dis[i][u] + 1){
                    dis[i][v.first] = dis[i][u] + 1;
                    we.push(v.first);
                }
            }
        }
    }
    for(int i = 1; i <= q; i++){
        ans[i] = dis[ask[i].first][ask[i].second.first];
        if(ans[i] > m)
            ans[i] = -1;
    }
}
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> q;
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        special[x] = 1;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges[w] = {u, v};
    }
    for(int i = 1; i <= q; i++){
        int x, d;
        cin >> x >> d;
        ask[i] = {d, {x, i}};
    }
    sub3::solve();
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    return 0;
}

import sys
from collections import deque
def main():
    data = sys.stdin.buffer.read().split()
    n, m, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    p = 4
    srcs = [int(x) for x in data[p:p + k]]   # tất cả điểm đặc biệt
    p += k
    ad = [[] for _ in range(n + 1)]
    for i in range(m):
        u, v, c = int(data[p]), int(data[p + 1]), int(data[p + 2])
        p += 3
        ad[u].append((v, c))
        ad[v].append((u, c))
    INF = 10 ** 9
    dis = [None] * 11
    for i in range(1, 11):                # BFS đa nguồn trên đồ thị cạnh là bội của i
        d = [INF] * (n + 1)
        for s in srcs:
            d[s] = 0
        we = deque(srcs)
        while we:
            u = we.popleft()
            for v, c in ad[u]:
                if c % i:
                    continue
                if d[v] > d[u] + 1:
                    d[v] = d[u] + 1
                    we.append(v)
        dis[i] = d
    out = []
    for _ in range(q):
        x, D = int(data[p]), int(data[p + 1])
        p += 2
        r = dis[D][x]
        out.append(-1 if r > m else r)
    print('\n'.join(map(str, out)))
main()

C++▶ Chạy tay từng dòng codeSubtask 3: BFS đa nguồn từ mọi điểm đặc biệt cho từng i = 1..10.

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;

3int n, m, k, q;

4bool special[300005];

5int ans[300005];

6pair<int, int> edges[1000005];

7int deg[300005];

8pair<int, pair<int, int>> ask[300005];

9namespace sub3 {

10int dis[15][300005];

11vector<vector<pair<int, int>>> ad(300005);

12void solve(){

13 for(int i = 1; i <= 1000000; i++){

14 if(edges[i].first != 0){

15 ad[edges[i].first].push_back({edges[i].second, i});

16 ad[edges[i].second].push_back({edges[i].first, i});

17 }

18 }

19 for(int i = 1; i <= 10; i++){

20 queue<int> we;

21 for(int j = 1; j <= n; j++)

22 dis[i][j] = 1e9;

23 for(int j = 1; j <= n; j++)

24 if(special[j]){

25 we.push(j);

26 dis[i][j] = 0;

27 }

28 while(!we.empty()){

29 int u = we.front();

30 we.pop();

31 for(auto v : ad[u]){

32 if(v.second % i)

33 continue;

34 if(dis[i][v.first] > dis[i][u] + 1){

35 dis[i][v.first] = dis[i][u] + 1;

36 we.push(v.first);

37 }

38 }

39 }

40 }

41 for(int i = 1; i <= q; i++){

42 ans[i] = dis[ask[i].first][ask[i].second.first];

43 if(ans[i] > m)

44 ans[i] = -1;

45 }

46}

47};

48int main(){

49 ios::sync_with_stdio(0);

50 cin.tie(0);

51 cin >> n >> m >> k >> q;

52 for(int i = 1; i <= k; i++){

53 int x;

54 cin >> x;

55 special[x] = 1;

56 }

57 for(int i = 1; i <= m; i++){

58 int u, v, w;

59 cin >> u >> v >> w;

60 edges[w] = {u, v};

61 }

62 for(int i = 1; i <= q; i++){

63 int x, d;

64 cin >> x >> d;

65 ask[i] = {d, {x, i}};

66 }

67 sub3::solve();

68 for(int i = 1; i <= q; i++)

69 cout << ans[i] << '\n';

70 return 0;

71}

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

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

100%Subtask 4, 5: gom truy vấn theo D, xử lý offline

Có thể thấy, với 1 đồ thị vô hướng bất kì, ta có thể thực hiện multisource BFS từ các đỉnh đặc biệt để tính khoảng cách ngắn nhất từ 1 đỉnh đến 1 đỉnh đặc biệt, và từ đó ta có thể trả lời truy vấn trong $O(1)$.

Nhưng giờ $D$ lớn, không thể tính trước cho mọi $D$ được. Để giải quyết subtask cuối cùng, ta sẽ trả lời các truy vấn offline (đọc hết truy vấn vào trước rồi mới xử lý, không cần trả lời theo đúng thứ tự đọc vào):

Sắp xếp các truy vấn theo $D$ để các truy vấn có cùng giá trị $D$ đứng cạnh nhau.
Với mỗi giá trị $d$ có xuất hiện trong truy vấn, ta sẽ xét tất cả các cạnh có trọng số là bội của $d$ (nhảy $c = d, 2d, 3d, \ldots$ trên mảng edges), dựng đồ thị con chỉ gồm các cạnh đó, sau đó thực hiện BFS đa nguồn và trả lời tất cả các truy vấn cùng giá trị $d$ trong $O(1)$ mỗi truy vấn.
Dọn dẹp đồ thị con (chỉ dọn những đỉnh đã dùng) rồi chuyển sang giá trị $d$ tiếp theo.

Em nhập đồ thị và các lượt chơi rồi bấm Tiếp để xem từng giá trị $D$ được xử lý thế nào:

N: Điểm đặc biệt: Cạnh u-v-c: Lượt chơi X-D:

Ví dụ nhanh:

Vì sao đủ nhanh?

Có thể thấy, tổng số cạnh được xét đến trong tất cả các giá trị $d$ là không quá

$\dfrac{A}{1} + \dfrac{A}{2}$ $+ \dfrac{A}{3}$ $+ \ldots + \dfrac{A}{A} \quad (A = 10^6)$

vì với mỗi $d$ ta chỉ nhảy $A / d$ lần trên mảng edges (và mỗi $d$ chỉ xử lý 1 lần dù có bao nhiêu truy vấn cùng $d$). Đây là tổng điều hoà, xấp xỉ $A \ln A$. Mà vì số đỉnh chúng ta cần xét đến không quá 2 lần số cạnh, nên ta được thuật toán có độ phức tạp cuối cùng là

$O\left(\dfrac{A}{1} + \dfrac{A}{2} + \dfrac{A}{3} + \ldots + \dfrac{A}{A}\right)$ $= O(A \log A)$

Tuy nhiên, giới hạn thời gian cho bài này vẫn còn rất chặt, nên chúng ta sẽ cần tối ưu về mặt hằng số cho code. Mình liệt kê nhanh các tối ưu trong code mẫu để các bạn dễ đọc:

Hàng đợi tự làm bằng mảng we[] với con trỏ ps (đầu) và len (cuối), không dùng queue của STL.
Không reset cả mảng sau mỗi $d$: mảng node[] ghi lại các đỉnh đã xuất hiện trong đồ thị con (nhờ deg đếm bậc, đỉnh nào bậc vừa lên 1 là đỉnh mới), cuối lượt chỉ dọn đúng các đỉnh đó: trả dis về $10^9$ (trừ điểm đặc biệt giữ $0$), deg = 0, ad.clear().
Chỉ những giá trị $d$ có truy vấn mới được xử lý (câu if(j2 <= q && ask[j2].first == i)), các $d$ khác bỏ qua ngay.
Đỉnh không nằm trong đồ thị con thì dis vẫn là giá trị "vô cực" ($0x3f3f3f3f$ hoặc $10^9$, đều $> M$) nên in $-1$; còn nếu chính $X$ là điểm đặc biệt thì dis[X] = 0, in $0$, đúng ý đề.

Code 100% – gom truy vấn theo D, BFS đa nguồn offline

#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
bool special[300005];
int ans[300005];
pair<int, int> edges[1000005];
int deg[300005];
pair<int, pair<int, int>> ask[300005];
namespace sub5 {
int dis[300005];
int node[300005];
int we[300005];
vector<int> ad[300005];
void solve(){
    sort(ask + 1, ask + 1 + q, greater<pair<int, pair<int, int>>>());
    int j2 = 1;
    //Solve all queries
    memset(dis, 0x3f, sizeof(dis));
    for(int i = 1; i <= n; i++)
        if(special[i] == 1)
            dis[i] = 0;
    for(int i = 1e6; i >= 1; i--)
        if(j2 <= q && ask[j2].first == i){
            int gg = 1;
            int len = 0;
            for(int j = 1; i * j <= 1e6; j++){
                pair<int, int> k = edges[i * j];
                if(k.first == 0)
                    continue;
                if(++deg[k.first] == 1){
                    node[gg++] = k.first;
                    if(special[k.first] == 1){
                        we[++len] = k.first;
                        dis[k.first] = 0;
                    }
                }
                if(++deg[k.second] == 1){
                    node[gg++] = k.second;
                    if(special[k.second] == 1){
                        we[++len] = k.second;
                        dis[k.second] = 0;
                    }
                }
                ad[k.first].push_back(k.second);
                ad[k.second].push_back(k.first);
            }
            int ps = 1;
            while(ps <= len){
                int u = we[ps++];
                for(auto v : ad[u])
                    if(dis[v] > dis[u] + 1){
                        dis[v] = dis[u] + 1;
                        we[++len] = v;
                    }
            }
            while(j2 <= q && ask[j2].first == i){
                int x = ask[j2].second.first, idx = ask[j2].second.second;
                ans[idx] = dis[x];
                if(ans[idx] > m)
                    ans[idx] = -1;
                j2++;
            }
            for(int u = 1; u < gg; u++){
                if(dis[node[u]] > 0)
                    dis[node[u]] = 1e9;
                deg[node[u]] = 0;
                ad[node[u]].clear();
            }
        }
}
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k >> q;
    for(int i = 1; i <= k; i++){
        int x;
        cin >> x;
        special[x] = 1;
    }
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        edges[w] = {u, v};
    }
    for(int i = 1; i <= q; i++){
        int x, d;
        cin >> x >> d;
        ask[i] = {d, {x, i}};
    }
    sub5::solve();
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
    return 0;
}

import sys
def main():
    data = sys.stdin.buffer.read().split()
    n, m, k, q = int(data[0]), int(data[1]), int(data[2]), int(data[3])
    p = 4
    special = [False] * (n + 1)
    for i in range(k):
        special[int(data[p + i])] = True
    p += k
    A = 10 ** 6
    eu = [0] * (A + 1)
    ev = [0] * (A + 1)
    for i in range(m):
        u, v, c = int(data[p]), int(data[p + 1]), int(data[p + 2])
        p += 3
        eu[c] = u
        ev[c] = v
    byd = {}                              # gom truy vấn theo D (offline)
    for i in range(q):
        x, D = int(data[p]), int(data[p + 1])
        p += 2
        byd.setdefault(D, []).append((x, i))
    INF = 10 ** 9
    dis = [INF] * (n + 1)
    for i in range(1, n + 1):
        if special[i]:
            dis[i] = 0
    ad = [[] for _ in range(n + 1)]
    ans = [0] * q
    for D, qs in byd.items():
        nodes = []
        for c in range(D, A + 1, D):      # chỉ xét các cạnh có mã khóa là bội của D
            u = eu[c]
            if u == 0:
                continue
            v = ev[c]
            if not ad[u]:
                nodes.append(u)
            if not ad[v]:
                nodes.append(v)
            ad[u].append(v)
            ad[v].append(u)
        we = [x for x in nodes if special[x]]   # BFS đa nguồn từ các điểm đặc biệt
        ps = 0
        while ps < len(we):
            u = we[ps]
            ps += 1
            du = dis[u] + 1
            for v in ad[u]:
                if dis[v] > du:
                    dis[v] = du
                    we.append(v)
        for x, idx in qs:
            ans[idx] = -1 if dis[x] > m else dis[x]
        for u in nodes:                   # dọn dẹp cho lượt D tiếp theo
            if not special[u]:
                dis[u] = INF
            ad[u] = []
    sys.stdout.write('\n'.join(map(str, ans)) + '\n')
main()

C++▶ Chạy tay từng dòng codeCode 100%: gom truy vấn theo D, mỗi D dựng đồ thị con từ các bội của D rồi BFS đa nguồn.

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;

3int n, m, k, q;

4bool special[300005];

5int ans[300005];

6pair<int, int> edges[1000005];

7int deg[300005];

8pair<int, pair<int, int>> ask[300005];

9namespace sub5 {

10int dis[300005];

11int node[300005];

12int we[300005];

13vector<int> ad[300005];

14void solve(){

15 sort(ask + 1, ask + 1 + q, greater<pair<int, pair<int, int>>>());

16 int j2 = 1;

17 //Solve all queries

18 memset(dis, 0x3f, sizeof(dis));

19 for(int i = 1; i <= n; i++)

20 if(special[i] == 1)

21 dis[i] = 0;

22 for(int i = 1e6; i >= 1; i--)

23 if(j2 <= q && ask[j2].first == i){

24 int gg = 1;

25 int len = 0;

26 for(int j = 1; i * j <= 1e6; j++){

27 pair<int, int> k = edges[i * j];

28 if(k.first == 0)

29 continue;

30 if(++deg[k.first] == 1){

31 node[gg++] = k.first;

32 if(special[k.first] == 1){

33 we[++len] = k.first;

34 dis[k.first] = 0;

35 }

36 }

37 if(++deg[k.second] == 1){

38 node[gg++] = k.second;

39 if(special[k.second] == 1){

40 we[++len] = k.second;

41 dis[k.second] = 0;

42 }

43 }

44 ad[k.first].push_back(k.second);

45 ad[k.second].push_back(k.first);

46 }

47 int ps = 1;

48 while(ps <= len){

49 int u = we[ps++];

50 for(auto v : ad[u])

51 if(dis[v] > dis[u] + 1){

52 dis[v] = dis[u] + 1;

53 we[++len] = v;

54 }

55 }

56 while(j2 <= q && ask[j2].first == i){

57 int x = ask[j2].second.first, idx = ask[j2].second.second;

58 ans[idx] = dis[x];

59 if(ans[idx] > m)

60 ans[idx] = -1;

61 j2++;

62 }

63 for(int u = 1; u < gg; u++){

64 if(dis[node[u]] > 0)

65 dis[node[u]] = 1e9;

66 deg[node[u]] = 0;

67 ad[node[u]].clear();

68 }

69 }

70}

71};

72int main(){

73 ios::sync_with_stdio(0);

74 cin.tie(0);

75 cin >> n >> m >> k >> q;

76 for(int i = 1; i <= k; i++){

77 int x;

78 cin >> x;

79 special[x] = 1;

80 }

81 for(int i = 1; i <= m; i++){

82 int u, v, w;

83 cin >> u >> v >> w;

84 edges[w] = {u, v};

85 }

86 for(int i = 1; i <= q; i++){

87 int x, d;

88 cin >> x >> d;

89 ask[i] = {d, {x, i}};

90 }

91 sub5::solve();

92 for(int i = 1; i <= q; i++)

93 cout << ans[i] << '\n';

94 return 0;

95}

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

Thời gian$O(A \log A + Q \log Q)$

Lưu ý nhỏ của mình

Vòng for(int i = 1e6; i >= 1; i--) chạy $i$ từ $10^6$ trở xuống, nên code ngầm hiểu $D \le 10^6$ (khớp với mã khóa $c \le 10^6$). Đề không ghi rõ giới hạn của $D$ ở subtask cuối; nếu lỡ có $D > 10^6$ thì chìa đó không mở được cửa nào, đáp án là $0$ nếu $X$ là điểm đặc biệt, ngược lại là $-1$. Bạn nào muốn chắc ăn thì xử lý riêng trường hợp này trước khi sort nhé.

Ghi chú kiểm tra của mình: 4 code C++ là code mẫu của từng subtask, các bản Python là mình viết thêm. Mình đã kiểm tra mỗi code với 220 bộ test ngẫu nhiên đúng ràng buộc subtask của nó ($N \le 8$, $M \le 12$, mã khóa nhỏ để có nhiều bội chung, có cả trường hợp $X$ là điểm đặc biệt và trường hợp in $-1$) so với chương trình vét cạn (mỗi truy vấn lọc cạnh rồi BFS lại từ đầu): khớp 100%. Thời gian trên máy mình với $N = M = Q = 3 \times 10^5$: Subtask 1 khoảng 0.14 giây, Subtask 2 khoảng 0.31 giây, Subtask 3 khoảng 0.44 giây, code 100% khoảng 0.64 giây với $3 \times 10^5$ giá trị $D$ khác nhau (trường hợp tổng điều hoà lớn nhất). Bản Python của subtask 1–3 chạy 0.4–1.2 giây, còn bản Python 100% mất khoảng 11 giây ở test xấu nhất, nên với bài này các bạn nên dùng C++.

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

Hội Chợ

Đề bài

Lời mở đầu

Subtask 1Q = 1, D = 1: BFS từ đỉnh xuất phát

Subtask 2K = 1, D ≤ 10: BFS ngược từ điểm đặc biệt

Subtask 3D ≤ 10: BFS đa nguồn (multi-source BFS)

100%Subtask 4, 5: gom truy vấn theo D, xử lý offline

Vì sao đủ nhanh?

Nhận xét

Đăng nhận xét

Khóa học Lập trình Thuật toán thi đấu

Lộ trình học thuật toán từ A đến Z

Thành tích học viên