Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #3

Coding Challenge #3 là một bài toán về đường đi ngắn nhất, với tập cạnh có trọng số. Bài toán này là phiên bản tổng quát hoá trên đồ thị của bài toán đổ xăng nổi tiếng mà ắt hẳn mọi người đều đã trải qua một lần. Điểm thú vị của dạng bài này chính là việc chúng ta sẽ cần tư duy để tạo ra một đồ thị mới nhằm có thể nắm đủ thông tin bài toán. Trong 3 Coding Challenge, đây chính là bài toán thử thách nhất.

Bài toán này ghi nhận 21 bài giải thành công với lời giải nhanh nhất chỉ tốn 43 phút kể từ lúc đề bài Coding Challenge #3 được công bố. Đội ngũ Tạp chí VNOI đã chọn ra 2 lời giải cho bài toán này đến từ các độc giả của Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ

Coding Challenge #3 - Đổ Xăng

Đổ Xăng

Vương quốc VNOI gồm ~n~ thành phố được liên kết với nhau bằng ~m~ con đường hai chiều, đảm bảo rằng mọi cặp thành phố đều có đường đi trực tiếp hoặc gián tiếp tới nhau. Con đường thứ ~i~ kết nối hai thành phố ~u_i, v_i~, và sẽ tốn ~w_i~ lít xăng để đi qua.

Là một người đam mê du lịch, bạn lên kế hoạch cho chuyến đi chơi của mình tới VNOI. Bạn xuất phát từ thành phố ~st~ và có dự định đi tới thành phố ~en~ bằng xe của mình. Tất nhiên để đi xe thì phải tốn nhiên liệu, và xe của bạn có một bình chứa được tối đa ~t~ lít xăng.

VNOI có ~s~ trạm xăng. Trạm xăng thứ ~i~ được phân bố ở thành phố ~p_i~ và có chi phí cho mỗi lít xăng là ~c_i~. Ở mỗi trạm xăng, bạn có thể mua không giới hạn số xăng (tất nhiên xe bạn chỉ mang tối đa được ~t~ lít xăng thôi).

Bạn bắt đầu từ thành phố ~st~ và xe bạn ban đầu không có xăng - may mắn rằng đảm bảo luôn có trạm xăng ở thành phố nơi bạn xuất phát. Hãy tính số tiền ít nhất cần bỏ ra để hoàn thành hành trình từ ~st~ tới ~en~.

Input

• Dòng đầu gồm 3 số nguyên ~n, m, s~ (~2 \le n \le 1000; 1 \le m \le 10^4; 1 \le s \le 100~)
• Dòng tiếp theo gồm một số nguyên dương ~t~ (~1 \le t \le 10^5~) mô tả sức chứa của bình xăng.
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i, v_i, w_i~ (~1 \le u_i, v_i \le n; 1 \le w_i \le t~) miêu tả con đường thứ ~i~.
• ~s~ dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên dương ~p_i, c_i~ (~1 \le p_i \le n; 1 \le c_i \le 100~) miêu tả trạm xăng thứ ~i~.
• Dòng cuối cùng gồm hai số nguyên dương ~st, en~ (~1 \le st, en \le n~) miêu tả vị trí bắt đầu và đích đến của bạn.

Output

• In ra số tiền ít nhất cần để đi chuyến đi.

Subtask

• Subtask ~1~ (~30~\%): ~n \le 100~; ~m \le 100~; ~t \le 500~
• Subtask ~2~ (~30~\%): ~t \le 500~
• Subtask ~3~ (~40~\%): Không giới hạn gì thêm.

Sample Input 1

3 3 2
200
1 3 80
1 2 50
2 3 50
1 70
2 40
1 3

Sample Output 1

5500

Sample Input 2

5 5 3
100
1 2 80
2 5 80
1 3 40
3 4 60
4 5 60
1 8
2 9
3 2
1 5

Sample Output 2

1340

Sample Input 3

4 3 3
10
1 2 2
2 3 6
3 4 3
1 4
2 7
3 9
2 4

Sample Output 3

61

Minh Họa Sample:

Sample 1:

Sample 2

Sample 3

Lời giải #1

Subtask 1: ~n, m \leq 100, t \leq 500~

Tags: DP, Dijkstra, Auxiliary Graph

Ta gọi ~f_{i, j}~ là số tiền ít nhất cần trả để đi đến đỉnh ~i~ và còn lại ~j~ lít xăng.

Với mỗi đỉnh ~f_{i, j}~ đã được tính, ta có thể chuyển trạng thái như sau:

• Mua thêm lít xăng nếu như đỉnh i tồn tại cây xăng ~f_{i, next_j}~ ~(j < next_j <= t)~. ~f_{i, next_j} = f_{i, j} + (next_j - j) * minCost_i~ với ~minCost_i~ là chi phí nhỏ nhất để mua ~1~ lít xăng tại đỉnh ~i~.
• Chuyển đến đỉnh ~v~ kề ~i~ nếu như ~j >= w~. ~f_{v, j - w} = f_{u, j}~

Độ phức tạp: ~O((n \times t + (m + n \times t \times t)) \times log_2(n \times t))~

Subtask 2: ~t \leq 500~

Tags: Dijkstra, Auxiliary Graph.

Vẫn từ ý tưởng cũ, để dễ xử lí, ta tạo đỉnh ảo cho mỗi ~f_{i, j}~. Ở subtask 1, ta thấy rằng việc chuyển trạng thái cho ~f_{i, next_j}~ là khá lớn. Vậy nên, thay vì phải duyệt hết những ~next_j~, ta chỉ cần chuyển đến trạng thái ~f_{i, j + 1}~. Lúc này, số lượng cạnh cần xét sẽ giảm đi đáng kể !

Độ phức tạp: ~O((n \times t + (m + n \times t)) \times log_2(n \times t))~

Subtask 3: Không có giới hạn gì thêm

Tags: Dijkstra, Auxiliary Graph.

Ta thấy rằng thay vì xem xét tất cả những đỉnh trong đồ thị gốc, ta chỉ quan tâm đến những đỉnh đặc biệt, những đỉnh này là những đỉnh mà có thể ảnh hưởng đến hàm ~f~ của chúng ta. Đầu tiên, ta định nghĩa những đỉnh đặc biệt là những đỉnh hoặc là ~st~, hoặc là ~en~, hoặc là tồn tại ít nhất ~1~ cây xăng ở nó, và khi ta đến đỉnh đặc biệt, ta buộc phải mua lít xăng (nếu có cây xăng). Ta dễ dàng thấy được số lượng đỉnh đặc biệt là rất là ít, chỉ khoảng ~\leq 101~!. Vậy nên, Ta sẽ xem xét xem với cặp đỉnh ~(u, v)~ đặc biệt, chi phí thấp nhất để từ ~u \to v~ là bao nhiêu. Điều này ta có thể dễ dàng làm được bằng việc dijkstra trên đồ thị gốc. Ta gọi ~minCost_{u, v}~ là số lít nhỏ nhất để có thể đi từ ~u \to v~. Lúc này, hàm quy hoạch động của chúng ta giảm số lượng thái từ ~n \times t~ về ~s \times t~. Nhưng... vẫn còn quá lớn ?. Ta có một nhận xét quan trọng như sau: nếu khi đến đỉnh đặc biệt ~u~, vì ta buộc phải mua lít xăng ở ~u~, ta có thể giảm số trạng thái chiều ~j~ không phải là ~t~ mà là ~2 \times s~ (khoảng ~2 \times 10^4~, bé hơn ~t~ nhiều). Đầu tiên, ta quan sát rằng, khi tại đỉnh ~u~, ta chỉ nên mua đủ để đi đến ~v~ hoặc mua đầy tại ~u~ sau đó đi đến ~v~. Vậy nên, ta chỉ cần những trạng thái ~j~ hoặc là nằm trong tập ~\{minCost_{u, v}\}~, hoặc là nằm trong tập ~\{t - minCost_{u, v} \}~. Mà ta thấy số lượng phần tử trong của tập ~\{minCost_{u, v}\} \leq 10^4~ (Ta sẽ gọi đây là tập ~j~ đặc biệt).

Chứng minh:

• Xét hai đỉnh đặc biệt (u, v). Ta chia thành ~2~ trường hợp như sau:
  • Trường hợp ~1~: ~minCost_u < minCost_v~. Lúc này, để tối ưu, ta nên mua đầy lít xăng (là mua để làm đầy sức chứa) ở tại đỉnh ~u~, sao đó di chuyển đến đỉnh ~v~. Thì chi phí của chúng ta mới tối ưu được (thay vì từ đỉnh ~u~ đi đến đỉnh ~v~ xong rồi mua xăng). (Là cách chuyển trạng thái ~j~ từ ~t \to t - w~)
  • Trường hợp ~2~: ~minCost_u > minCost_v~. Lúc này, nếu như trường hợp ta còn đủ lít xăng, ta không nên mua tại ~u~ mà ta đi thẳng đến ~v~ (thì chắc chắn ~f_{v, x}~ không được tính từ ~f_{u, y}~. Trong chiều hướng ngược lại, ta nên mua đủ số lít xăng tại đỉnh ~u~ xong rồi đi đến đỉnh ~v~. (Là cách chuyển trạng thái ~j~ từ ~w \to 0~)

Xét Sample Input 2 trong đề bài, từ các thông tin sau, ta có thể xây dựng đồ thị như trên:

• ~SpecialNodes = \{ 1,2,3,5 \}~.
• ~SpecialCosts = \{ 0,20,40,60,80,100 \}~.
• Số lít xăng cần ít nhất từ ~1 \to 2~, ~1 \to 3~, ~2 \to 5~ lần lượt là ~80, 40, 80~. Chi phí mua xăng ít nhất tại đỉnh ~1, 2, 3~ lần lượt là ~8, 9, 2~. Ở đồ thị ảo ta xây dựng ở Sample Input 2, đường màu xanh là đường đi tối ưu, chính vì thế kết quả của chúng ta là ~1340~ !

Cuối cùng, ta sẽ có thuật toán như sau: Ta gọi:

• ~specialNodes~, ~specialCosts~ lần lượt là ~i~ và tập ~j~ đặc biệt.
• ~f_{i, j}~ là chi phí thấp nhất để đến đỉnh ~specialNode_i~ và còn dư ~specialCost_j~ lít.
• ~minCost_i~: chi phí nhỏ nhất để mua ~1~ lít xăng tại đỉnh ~specialNode_i~.
• ~minCost_{u, v}~: chi phí để đi từ ~u~ đến ~v~ mà mất ít lít xăng nhất.

Dễ dàng tính được ~minCost{u, v}~ bằng thuật toán dijkstra trên đồ thị ban đầu. Bước tiếp theo, ta sẽ thêm các cạnh vào đồ thị ảo. - Ta sẽ thêm tập cạnh ~f(u, minCost_{u, v}) \to f(v, 0)~ với trọng số là ~0~ nếu ~minCost_{u, v} \leq t~ (với ~u, v~ là những đỉnh đặc biệt) vào đồ thị ảo thể hiện mình sẽ đi đến ~v~ với đủ lít xăng. - Ta tiếp tục thêm tập cạnh ~f(u, t) \to f(v, t - minCost_{u, v})~ với trọng số là ~0~ nếu ~minCost_{u, v} \leq t~ (với ~u, v~ là những đỉnh đặc biệt) vào đồ thị ảo thể hiện mình đi đến ~v~ với đầy lít xăng. - Cuối cùng, ta thêm tập cạnh ~(u, t) \to (u, t')~ với trọng số là ~(t' - t) * minCost_u~ thể hiện ta mua lít xăng tại đỉnh ~u~.

Cuối cùng, ta sử dụng thuật toán dijkstra trong đồ thị ảo để tìm kết quả.

Lời giải #2

Subtask 1

Giới hạn: ~n \le 100~; ~m \le 100~; ~t \le 500~

Ý Tưởng:

• Ta đặt ~\text{costs}[i]~ là chi phí nhỏ nhất để mua ~1~ lít xăng ở thành phố ~i~. Nếu thành phố thứ ~i~ không có trạm xăng nào thì ta có thể coi ~\text{cost}[i] = +\infty~.
• Ta có thể mô hình bài toán bằng cách dựng một đồ thị ~G = (V, E)~ với mỗi đỉnh trong ~G~ đại diện cho một trạng thái của xe, gồm:
  • Thành phố xe đang dừng; và
  • Lượng xăng xe đang có. Nói cách khác, mỗi đỉnh có thể được biển diễn bằng một cặp số ~(i, f)~ với ~i~ là số hiệu thành phố và ~f~ là lượng xăng hiện tại của xe (~1 \leq i \leq n~, ~0 \leq f \leq t~).
• Ta sẽ có hai loại cạnh dựa trên hai loại hành động:
  • Mua ~1~ lít xăng: đồ thị chứa cạnh từ ~(i, f)~ đến ~(i, f + 1)~ (với điều kiện~f < t~) có trọng số ~\text{costs}[i]~.
  • Di chuyển sang thành phố khác trên con đường thứ ~i~: đồ thị chứa cạnh từ ~(u_i, r)~ đến ~(v_i, r - w_i)~ (với điều kiện ~r \geq w_i~) có trọng số ~0~.
• Kết quả bài toán ta cần tìm lúc này sẽ tương đương với việc tìm độ dài của đường đi ngắn nhất từ đỉnh ~(st, 0)~ đến một đỉnh ~(en, f)~ bất kì với ~0 \leq f \leq t~. Vì mọi trọng số đều không âm, ta dùng Dijkstra để tìm được độ dài ấy.

Độ Phức Tạp

• Ý tưởng nêu trên có thể được cài đặt với độ phức tạp thời gian ~O((|V| + |E|)\log |V|)~ nếu ta cài đặt thuật toán Dijkstra với heap.
  • Vì với mỗi thành phố, ta có ~t + 1~ trạng thái khác nhau đại diện cho các mức xăng khác nhau, ta có ~V = O(n \cdot t)~ .
  • Vì với mỗi đường đi, ta sẽ có ~O(t)~ cạnh loại thứ hai được nêu trên và với mỗi thành phố, ta sẽ có ~O(t)~ cạnh loại thứ nhất được nếu trên, ta có ~E = O((n + m) \cdot t)~.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace Dijkstra {

    signed minimumCosts[MAX_N][MAX_T];
    priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > heap;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c))
            heap.emplace(c, make_pair(v, r));
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !heap.empty();) {
            const auto [m, state] = heap.top();
            const auto &[x, r] = state;
            heap.pop();

            if (minimumCosts[x][r] != m)
                continue;

            if (x == en) {
                cout << m << '\n';
                return;
            }

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    Dijkstra::run();

    return 0;
}

Subtask 2

Giới hạn: ~n \le 1000~; ~m \le 10^4~; ~t \le 500~

Ý Tưởng:

• Vì chương trình giải cần phải chạy trong ~1~ giây (tương đương với khoảng ~10^8~ lệnh), giới hạn của subtask 2 có thể khiến chương trình chạy quá thời gian khi sử dụng thuật toán Dijkstra như trong subtask 1. Một thuật toán thay thế để tìm đường đi ngắn nhất ta có thể sử dụng để tìm đường đi ngắn nhất là SPFA (Shortest Path Faster Algorithm).

Độ Phức Tạp:

• Trong trường hợp tệ nhất, chương trình cài đặt với thuật toán SPFA có thể đạt độ phức tạp thời gian ~O(|V| \cdot |E|)~. Tuy nhiên, thời gian chạy trung bình của SPFA là rất nhanh, có thể được xem như thuật toán chạy với độ phức tạp ~O(|E|)~ trong trường hợp này.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;


vector<pair<int, int> > graph[MAX_N];
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
    }

    cin >> st >> en;
}

namespace SPFA {

    signed minimumCosts[MAX_N][MAX_T];
    bool inqueue[MAX_N][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == en)
                minimize(result, c);
            if (!inqueue[v][r]) {
                q.emplace(v, r);
                inqueue[v][r] = true;
            }
        }
    }

    void run() {
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(st, 0, 0);

        for (int x = 1; x <= n; ++x)
            sort(graph[x].begin(), graph[x].end());

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            for (const auto &[w, y] : graph[x]) {
                if (r < w)
                    break;
                considerVertex(y, r - w, minimumCosts[x][r]);
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + costs[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    SPFA::run();

    return 0;
}

Subtask 3

Giới hạn: ~n \le 1000~; ~m \le 10^4~; ~t \le 10^5~

Ý Tưởng:

• Cách dựng đồ thị như trong hai Subtask đầu đều sẽ dẫn đến số lượng đỉnh và cạnh lớn trong Subtask 3 (trong trường hợp tệ nhất, ~|V|~ và ~|E|~ có thể lần lượt đạt khoảng ~10^8~ và hơn ~10^9~).
• Tạm không xét đến chi tiết giá xăng, ta đặt ~G_0 = (V_0, E_0)~ là đồ thị vô hướng có trọng số với mỗi đỉnh đại diện cho một thành phố và mỗi cạnh đại diện cho một đường đi ban đầu (~|V_0| = n~, ~|E_0| = m~).
• Ta nhận thấy rằng không phải thành phố nào cũng có trạm xăng. Vì vậy để giảm số đỉnh cần xem xét, ta có thể mô hình bài toán theo một cách khác như sau: Ta đặt ~G_1 = (V_1, E_1)~ là một đầy đủ với:
  • mỗi đỉnh đại diện cho một thành phố có trạm xăng hoặc là đich đến. ~\Rightarrow |V_1| = O(s)~
  • mỗi cạnh có trọng số đại diện cho lượng xăng tối thiểu cần dùng để di chuyển giữa hai đỉnh nếu bình chứa là vô hạn (trọng số này tương đương với đường đi ngắn nhất trong ~G_0~). ~\Rightarrow |E_1| = O(s^2)~
• Nếu ta xét thêm chi tiết giá xăng, ta có thể dựng một đồ thị ~G' = (V', E')~ từ ~G_1~ như cách ta có thể dựng đồ thị ~G~ từ ~G_0~ (bằng cách thêm chi tiết lượng xăng vào trạng thái, ...).
  • Khi này, số lượng đỉnh tối đa sẽ được giảm xuống còn khoảng ~10^7~ (~|V'| = O(s \cdot t)~).
  • Tuy nhiên, số lượng cạnh vẫn quá lớn để xử lý (~|E'| = O(s^2 \cdot t)~ lớn hơn ~10^9~)
• Để giảm số lượng cạnh cần xét, ta có một số nhận xét như sau: Trong ~G_1~, xét một cung từ ~x~ tới ~y~ với trọng số ~w~,
  • Nếu ~\text{costs}[x] \geq \text{costs}[y]~ hoặc ~y~ là đích đến thì trong ~G'~, ngoại trừ cạnh từ ~(x, w)~ đến ~(y, 0)~, ta không cần phải xem xét bất kì cạnh nào khác giữa từ thành phố ~x~ đến ~y~.

Giải thích:

  Trong cả hai trường hợp, ta không có lý do để cần có nhiều hơn ~w~ lít xăng ở thành phố ~x~ bởi:
  - Với trường hợp đầu, ta có thể mua xăng với giá rẻ hơn ở thành phố ~y~ (nếu ta không mua xăng ở thành phố ~y~ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong ~V_1~ từ ~x~).
  - Với trường hợp sau, ta không đi thêm bất kì đâu khi đã đến đích.

• Nếu ~\text{costs}[x] < \text{costs}[y]~ thì trong ~G'~, ngoại trừ cạnh từ ~(x, t)~ đến ~(y, t - w)~, ta không cần phải xem xét bất kì cạnh nào khác từ thành phố ~x~ đến ~y~.

Giải thích:

  Ta không có lý do để cần có ít hơn ~t~ lít xăng ở thành phố ~x~ bởi:
  - Nếu ta không mua xăng ở thành phố ~y~ thì điều này đồng nghĩa với việc, ta muốn đến thành phố khác trong ~V_1~ từ ~x~ (vì ~G_1~ là một đồ thị đầy đủ được định nghĩa như trên).
  - Nếu ta mua xăng ở thành phố ~y~ nhưng lại rời thành phố ~x~ với lượng xăng không đầy bình, chi phí sẽ không được tối ưu bởi thay vì mua ~1~ lít xăng ở ~y~, ta có thể làm điều tương tự với chi phí rẻ hơn ở thành phố ~x~.

• Với những nhất xét này, số lượng cạnh cần xét sẽ giảm xuống ~|E_2| = O(s^2 + s \cdot t)~ bởi ta chỉ xét tối đa một cạnh giữa hai thành phố khác nhau trong ~G_1~.

Mở rộng:

Số lượng cạnh và đỉnh cần xét có thể tiếp tục được giảm xuống ~O(s^2)~ bằng cách chỉ xét những đỉnh ~(x, f)~ có tối thiểu một cạnh đến đỉnh đại diện cho một thành phố khác ~x~.

Độ Phức Tạp:

• Để dựng được đồ thị ~G_1~, ta có thể cài đặt bằng cách chạy thuật toán Dijkstra nhiều lần với các thành phố có trạm xăng làm đỉnh nguồn. Vì vậy, bước này sẽ có độ phức tạp thời gian ~O(s \cdot n \cdot \log (n + m))~.
• Nếu ta tiếp tục sử dụng thuật toán SPFA trên đồ thị ~G_2 = (V_1, E_2)~, bước tìm kết quả cuối cùng sẽ có độ phức tạp ~O(s^2 + s \cdot t)~. Vì thế độ phức tạp tổng cho các bước xử lý chính có thể được xem như ~O(s \cdot n \cdot \log(n + m) + s^2 + s \cdot t)~.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

template<class A, class B>
bool minimize(A &a, const B &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 1'003, MAX_S = 102, MAX_T = 1E5 + 5, INF = 0X3F3F3F3F;

vector<pair<int, int> > graph[MAX_N];
long long minimumCost = INF;
int n, m, s, t, st, en;
signed costs[MAX_N];

void input() {
    int u = 0, v = 0, w = 0, p = 0, c = 0;

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= n; ++i)
        costs[i] = INF;

    for (int e = 1; e <= m; ++e) {
        cin >> u >> v >> w;
        graph[u].emplace_back(w, v);
        graph[v].emplace_back(w, u);
    }

    for (int i = 1; i <= s; ++i) {
        cin >> p >> c;
        minimize(costs[p], c);
        minimize(minimumCost, c);
    }

    cin >> st >> en;
}

namespace DijkstraAlgorithm {

    int vertexCount, vertexID[MAX_N], minimumDistances[MAX_S][MAX_S];
    vector<int> vertices, prices;

    void findMinimumDistances(const int source) {
        priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
        vector<int> distances(n + 1, INF);
        heap.emplace(distances[source] = 0, source);
        for (; !heap.empty();) {
            const auto [d, x] = heap.top();
            heap.pop();
            for (const auto &[w, y] : graph[x])
                if (minimize(distances[y], distances[x] + w))
                    heap.emplace(distances[y], y);
        }
        for (const int &destination : vertices)
            minimumDistances[vertexID[source]][vertexID[destination]] = distances[destination];
    }

    void run() {
        for (int i = 1; i <= n; ++i)
            if (costs[i] < INF || i == en) {
                vertexID[i] = (vertexCount++);
                vertices.push_back(i);
            } else
                vertexID[i] = -1;
        prices.resize(vertexCount);
        for (int i = 0; i < vertexCount; ++i) {
            findMinimumDistances(vertices[i]);
            prices[i] = costs[vertices[i]];
        }
    }

}

namespace SPFA {

    using namespace DijkstraAlgorithm;

    unordered_map<int, unordered_map<int, vector<int> > > graph;
    int endVertex, minimumCosts[MAX_S][MAX_T];
    bool inqueue[MAX_S][MAX_T];
    queue<pair<int, int> > q;
    int result = INF;

    void considerVertex(const int v, const int r, const int c) {
        if (minimize(minimumCosts[v][r], c) && c < result) {
            if (v == endVertex)
                result = c;
            else if (!inqueue[v][r]) {
                inqueue[v][r] = true;
                q.emplace(v, r);
            }
        }
    }

    void buildGraph() {
        endVertex = vertexID[en];
        for (int x = 0, y = 0; x < vertexCount; ++x)
            for (y = 0; y < vertexCount; ++y) {
                if (x == y || minimumDistances[x][y] > t)
                    continue;
                if (prices[x] >= prices[y] || y == endVertex) {
                    graph[x][minimumDistances[x][y]].push_back(y);
                    continue;
                }
                graph[x][t].push_back(y);
            }
    }

    void run() {
        buildGraph();
        memset(minimumCosts, INF, sizeof(minimumCosts));
        considerVertex(vertexID[st], 0, 0);

        for (; !q.empty(); q.pop()) {
            const auto &[x, r] = q.front();
            inqueue[x][r] = false;

            const auto outerElement = graph.find(x);

            if (outerElement != graph.end()) {
                const auto &innerElements = (outerElement -> second);
                const auto innerElement = innerElements.find(r);

                if (innerElement != innerElements.end()) {
                    for (const auto &y : (innerElement -> second))
                        considerVertex(y, r - minimumDistances[x][y], minimumCosts[x][r]);
                }
            }

            if (r + 1 <= t)
                considerVertex(x, r + 1, minimumCosts[x][r] + prices[x]);
        }

        cout << result << '\n';
    }

}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    DijkstraAlgorithm::run();
    SPFA::run();

    return 0;
}

Xin trân trọng cảm ơn các tác giả đã đồng hành cùng chuyên mục. Các tác giả có bài giải được đăng trong Tạp chí VNOI - Số 1 đã được đội ngũ Tạp chí VNOI liên hệ để nhận phần quà tri ân từ VNOI.

Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #2

Coding Challenge #2 tiếp tục là một bài toán đồ thị, với chủ đề về Cây Khung Nhỏ Nhất. Điểm đặc biệt của bài toán chính là ở việc chúng ta sẽ không chỉ đi tìm một cây khung, mà cần liên tiếp thực hiện thao tác tìm kiếm để cho ra K cây khung lớn nhất (một biến thể ngược của bài toán MST nổi tiếng).

Bài toán này ghi nhận 116 độc giả tham gia giải và 28 bài giải được trọn vẹn 100/100 điểm từ bộ test. Đội ngũ Tạp chí VNOI đã chọn ra 2 lời giải cho bài toán này đến từ các độc giả của Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ

Coding Challenge #2 - Đấu Thầu

Nước VNOI gồm ~n~ thành phố và đang có kế hoạch liên kết chúng bằng ~m~ con đường cao tốc hai chiều. Các con đường được đánh số từ 1 tới ~m~, con đường thứ ~i~ liên kết thành phố ~u_i~ với ~v_i~, và có lợi nhuận là ~w_i~ (các giá trị ~w_i~ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền VNOI quyết định giao việc này cho ~k~ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ ~1~ tới ~k~ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong ~m~ đường cao tốc có sẵn trong kế hoạch, sao cho chúng không tạo ra bất kì chu trình nào và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường ~\{1 \to 2; 2 \to 3; 3 \to 1; 4 \to 5\}~ là không thoả mãn, bởi vì có chu trình ~1 \to 2 \to 3 \to 1~. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ ~1~ sẽ được chọn trước, sau đó tới nhà thầu thứ ~2~, ... tới nhà thầu thứ ~k~. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới tổng lợi nhuận lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền VNOI xem mỗi nhà thầu từ ~1~ tới ~k~ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

Input

• Dòng đầu tiên gồm 3 số nguyên ~n, m, k~ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu;
• ~m~ dòng tiếp theo, dòng thứ ~i~ gồm ~3~ số nguyên ~u_i, v_i, w_i~ miêu tả con đường thứ ~i~ trong kế hoạch, kết nối thành phố ~u_i~ với ~v_i~

Output

• Gồm ~k~ dòng, dòng thứ ~i~ chứa giá trị là tổng lợi nhuận của nhà thầu thứ ~i~ trong cách chia tối ưu.

Subtask

• Trong tất cả các test ~w_i \le 10^9~
• Có ~20~% test tương ứng ~20~% số điểm có ~n \le 10^5, m \le 5 \times 10^5; k = 1~.
• Có ~25~% test tương ứng ~25~% số điểm có ~n \le 10^3, m \le 10^4; k \le 1000~.
• Có ~35~% test tương ứng ~35~% số điểm có ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~.
• ~20~% số test còn lại tương ứng với ~20~ số điểm có ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~.

Sample

Sample 1

Input

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

Output

12

Sample 2

Input

5 8 3
1 2 9
2 3 8
3 4 7
2 5 4
1 3 3
2 4 2
4 5 6
1 5 5

Output

30
14
0

Tóm Tắt Đề Bài

• Cho một đồ thị vô hướng liên thông ~G = (V, E)~ có ~n~ đỉnh và ~m~ cạnh mang trọng số dương.
• Thực hiện thao tác sau ~k~ lần:
  • Tìm tập cạnh ~E' \subseteq E~ sao cho:
    • ~E'~ không chứa chu trình;
    • ~E'~ có tổng trọng số lớn nhất có thể.
  • Xóa các cạnh trong ~E'~ khỏi ~E~ (~E \leftarrow E \setminus E'~).
  • Cho biết tổng trọng số của ~E'~ sau mỗi lần thực hiện thao tác.

Minh Họa Sample

Sample 1:

• Minh hoạ đồ thị sau mỗi lần thực hiện thao tác

• Minh họa tập cạnh được chọn bởi các thao tác

Sample 2:

• Minh họa đồ thị sau mỗi lần thực hiện thao tác

• Minh họa tập cạnh được chọn bởi các thao tác

Lời giải #1

Một số lưu ý

Đồ thị được cho trên đề bài không nhắc đến việc không tồn tại cạnh lặp.

Subtask 1: ~n\le 10^5,m\le 5\times 10^5,k=1~

Theo đề bài, các cạnh mà mỗi nhà thầu chọn không được tạo thành một chu trình. Điều này tương ứng với việc các cạnh đó phải là các cạnh của một rừng (forest).

Trong subtask 1, chỉ có duy nhất một nhà thầu nên ta có thể tóm tắt yêu cầu của subtask này như sau: Chọn ra một tập cạnh có tổng trọng số lớn nhất sao cho tập cạnh đó phải tạo thành một rừng.

Đây là dạng bài toán tìm cây khung lớn nhất trên đồ thị. Về cơ bản thì cách làm không khác gì cách làm bài toán tìm cây khung nhỏ nhất.

Về thuật toán tìm cây khung nhỏ nhất, các bạn có thể tìm hiểu tại đây.

Độ phức tạp: ~O(m\times log(m)+m\times log(n))~ (Kruskal) hoặc ~O((m+n)\times log(n))~ (Prim).

Subtask 2: ~n\le 10^3,m\le 10^4,k\le 1000~

Trong trường hợp có nhiều nhà đấu thầu hơn, rõ ràng:

• Nhà đấu thầu thứ nhất sẽ chọn các cạnh để tạo thành cây khung lớn nhất (như subtask 1).
• Từ nhà đấu thầu thứ hai, họ cũng sẽ chọn các cạnh để tạo thành cây khung lớn nhất từ các cạnh còn lại mà họ có thể chọn.

Như vậy, subtask này chỉ là tìm cây khung lớn nhất ~k~ lần tương ứng với ~k~ nhà đấu thầu. Với mỗi lần chọn được các cạnh cho một nhà đấu thầu, ta bỏ các cạnh đó đi để xét cạnh trên đồ thị mới cho các nhà đấu thầu sau.

Độ phức tạp: ~O(T\times k)~ với ~T~ là độ phức tạp cho mỗi lần tìm cây khung lớn nhất (subtask 1).

Subtask 3: ~n\le 10^3,m\le 5\times 10^5,k\le 10^4~

Vì giới hạn lớn nên ta không thể áp dụng cách tìm cây khung lớn nhất như cách làm của subtask 1/2.

Dựa trên thuật toán Kruskal, ta có một cách làm khác để giải subtask 2 như sau:

• Ta tạo ~k~ cây khung tương ứng với ~k~ nhà đấu thầu. Sắp xếp lại các cạnh theo trọng số giảm dần.
• Khi xét từng cạnh, nếu cạnh đó có thể thêm vào cây khung thứ nhất thì ta sẽ thêm. Trong trường hợp ngược lại, ta sẽ xét cây khung thứ hai, và cứ vậy đến cây khung thứ ~k~ (chọn cây khung có chỉ số nhỏ nhất mà ta có thể thêm cạnh).
• Cách duyệt này vẫn đảm bảo việc chọn ra được cây khung lớn nhất cho tất cả ~k~ nhà đấu thầu.

Tới đây ta có một nhận xét:

• Gọi ~f(i,j,p)~ là hàm kiểm tra tính liên thông của cặp đỉnh ~(i,j)~ trên cây khung thứ ~p~. ~f(i,j,p)=1~ khi hai đỉnh này cùng nằm trên một TPLT của cây khung thứ ~p~ và ~f(i,j,p)=0~ trong trường hợp ngược lại.
• Khi đó, ~f(i,j,p)\ge f(i,j,p+1)\forall 1\le i,j\le n,1\le p<k>
• Nói cách khác, tính liên thông của mọi cặp đỉnh ~(i,j)~ giảm dần theo chỉ số ~p~ của cây khung.
</k>

Với tính chất của hàm ~f(i,j,p)~, ta có thể thực hiện tìm kiếm nhị phân để tìm cây khung có chỉ số nhỏ nhất mà ~f(i,j,p)=0~ mỗi khi xét cạnh ~(i,j)~.

Độ phức tạp cho mỗi lần xét cạnh sẽ là ~O(log(n)\times log(k))~ hoặc có thể nhỏ hơn nếu thực hiện tối ưu như nén đường đi hay gộp theo kích cỡ.

Độ phức tạp: ~O(m\times log(n)\times log(k))~.

Subtask 4: ~n\le 10^5,m\le 5\times 10^5,k\le 10^4~

Việc dựng ~k~ cây khung một cách thủ công sẽ không thể thực hiện như subtask 3 vì ~n\times k\le 10^9~, giới hạn này là rất lớn để có thể lưu trữ.

Trên thực tế, ta không cần phải lưu hết trạng thái của các đỉnh vì nếu có đỉnh không phải là một trong hai đầu của bất kỳ cạnh nào của cây khung thì không cần phải lưu trữ. Vì thế nên ta có thể sử dụng std::map hoặc cây tiền tố (trie) để lưu tất cả những nút cần lưu trữ thông tin. Điều này giúp việc thực hiện các thao tác trên DSU cũng chỉ mất ~O(log(n))~.

Lưu ý: Cần phải cài đặt cẩn thận vì có thể sẽ bị TLE (time limit exceed).

Độ phức tạp: ~O(m\times log(n)\times log(k))~.

Lời giải #2

Subtask 1: Giới hạn: ~n \le 10^5, m \le 5 \times 10^5; k = 1~

Ý Tưởng:

• Vì số thao tác cần phải thực hiện ~k~ là ~1~, bài toán có thể được quy về tìm cây khung lớn nhất (ngược với bài toán tìm cây khung nhỏ nhất) trong đồ thị đã cho bởi:
  • Vì tập cạnh được chọn, tạm gọi là ~E'~, không được chứa chu trình, ~E'~ phải là một rừng.
  • Hơn nữa, vì đồ thị ban đầu liên thông, để tổng trọng số là lớn nhất, ~E'~ phải là một cây khung (rừng liên thông gồm ~n - 1~ cạnh). Nếu ~E'~ không liên thông, ta có thể thêm một cạnh mới mà không tạo ra chu trình, làm tăng tổng trọng số. Điều này mâu thuẫn với giả thiết tối ưu.
• Để tìm cây khung lớn nhất, ta có thể sử dụng thuật toán Kruskal với một thay đổi nhỏ: Thay vì sắp xếp các cạnh theo thứ tự tăng dần trọng số, ta sắp xếp giảm dần.

Cách chứng minh thứ nhất (ngắn gọn):

• Bài toán tìm cây khung lớn nhất trên đồ thị ~G = (V, E)~ có thể được quy về bài toán tìm cây khung nhỏ nhất trên đồ thị ~G' = (V, E)~ với cùng tập đỉnh và cạnh, nhưng với trọng số mới được đảo dấu (~w'_e = -w_e~ cho mọi cạnh ~e \in E~). Khi đó, cây khung nhỏ nhất của ~G'~ cũng chính là cây khung lớn nhất của ~G~.
• Thuật toán Kruskal có thể được dùng để tìm cây khung nhỏ nhất với các cạnh được duyệt theo thứ tự trọng số tăng dần. Khi áp dụng thuật toán trên đồ thị ~G'~, thứ tự này tương đương với việc duyệt các cạnh của ~G~ theo thứ tự trọng số giảm dần.

Cách chứng minh thứ hai (chi tiết):

Lưu ý: Cách chứng minh này phần lớn giống với cách minh tính đúng đắn của thuật toán Kruskal.

• Ta có thể chứng minh tính đúng đắn của ý tưởng trên bằng cách chứng minh quy nạp theo số lượng cạnh đã chọn với mệnh đề sau: "Với tập cạnh ~M~ được chọn bởi thuật toán tại mọi thời điểm, đồ thị luôn chứa một cây khung lớn nhất với tập cạnh ~T~ chứa mọi cạnh của ~M~".

  • Trường hợp cơ sở: Mệnh đề trên hiển nhiên đúng với trường hợp ban đầu, khi ~M~ không chứa bất kì cạnh nào bởi tập rỗng luôn là tập con của bất kì cây khung lớn nhất nào.
  • Bước quy nạp: Khi ta xem xét có nên thêm cạnh ~e~ vào ~M~ đang thỏa mệnh đề trên không, ta có ba trường hợp sau:
  1. ~M \cup \{e\}~ chứa chu trình (thêm cạnh ~e~ vào ~M~ tạo nên một chu trình): Thuật toán sẽ không thêm ~e~ vào ~M~. Vì vậy, mệnh đề sẽ vẫn thỏa bởi ~T~ cũng không thể chứa ~e~ (~T~ là một cây khung nên không chứa chu trình).
  2. ~T~ chứa ~e~: Mệnh đề trên tiếp tục thỏa.
  3. ~T~ không chứa ~e~: Khi thêm cạnh ~e~ vào ~T~, ta có ~T \cup {e}~ chứa một chu trình duy nhất có chứa cạnh ~e~. Chu trình này phải chứa ít nhất một cạnh ~f~ không ở trong ~M~. Nếu không, việc thêm ~e~ vào ~M~ đã tạo chu trình, tức rơi vào trường hợp đầu tiên.

  Vì cạnh ~f~ đã không được chọn bởi thuật toán trước đó, trọng số của cạnh ~f~ không thể lớn hơn trọng số cạnh ~e~ (~w_f \leq w_e~). Khi này, ta nhận thấy rằng cây khung với tập cạnh ~T' = T \cup \{e\} \setminus \{f\}~ cũng là cây khung lớn nhất bởi tổng trọng số của ~T'~ không nhỏ hơn tổng trọng số của ~T~. Mệnh đề vì thế vẫn tiếp tục được thỏa bởi ~M \cup \{e\}~ là tập con của tập cạnh ~T'~ của một cây khung lớn nhất.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian ~O(m \log m + n)~ bằng cách sử dụng cấu trúc dữ liệu Disjoint Set Union để quản lý các thành phần liên thông như trong bài toán tìm cây khung nhỏ nhất.

Giải thích:

• Bước khởi tạo cấu trúc dữ liệu Disjoint Set Union có thể có độ phức tạp ~O(n)~.
• Bước sắp xếp cạnh có độ phức tạp ~O(m \log m)~.
• Với mỗi lần xem xét một cạnh ~e = (u, v)~, ta cần kiểm tra hai đỉnh của cạnh ~e~ có cùng thuộc một thành phần liên thông không và nếu không thuộc thì ta có gộp hai thành phần liên thông chứa ~u~ và ~v~ lại. Nếu ta cài đặt cấu trúc dữ liệu Disjoint Set Union với cả hai phương pháp gộp theo kính cỡ và nén đường đi, một lần xem xét thêm cạnh như trên có độ phức tạp ~O(\alpha(n))~ với ~\alpha~ là hàm Ackermann nghịch đảo.

Vì ta duyệt ~m~ cạnh, bước xém xét hết tất cả các cạnh sẽ có độ phức tạp ~O(m \cdot \alpha(n))~.

Độ phức tạp tổng lúc này sẽ là ~O(m \log m) + O(m \cdot \alpha(n)) + O(n) = O(m \log m + n)~.

Lưu ý: Nếu ta chỉ dùng một trong phương pháp nêu trên khi cài đặt cấu trúc dữ liệu Disjoint Set Union, một lần xem xét thêm cạnh như trên có độ phức tạp ~O(\log(n))~. Khi này, độ phức tạp tổng sẽ là ~O(m \cdot (\log(m) + \log(n)) + n)~.

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(n + m)~.

Giải thích:

• Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ.
• Cấu trúc dữ liệu Disjoint Set Union cần ~O(n)~ bộ nhớ.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges)
        if (dsu.unite(u, v))
            result += w;

    cout << result << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 2: Giới hạn: ~n \le 10^3, m \le 10^4; k \le 1000~

Ý Tưởng:

• Giới hạn của Subtask 2 cho phép chúng ta thực hiện ý tưởng đề cập trong Subtask 1 ~k~ lần mà vẫn đảm bảo được độ phức tạp thời gian cho phép. Cụ thể hơn, với mỗi thao tác, ta có thể thực hiện lại ý tưởng trong Subtask 1 rồi xóa tập cạnh được chọn bởi thao tác khỏi đồ thị để ta có thể xử lý các thao tác sau. >[!Note] Lưu ý: >Vì sau khi xóa cạnh khỏi đồ thị, đồ thị có thể không liên thông nữa, tập cạnh mà chúng ta cần tìm lúc này có thể là một rừng thay vì chỉ một cây khung: với mỗi thành phần liên thông trong đồ thị hiện tại, ta cần tìm cây khung lớn nhất trong thành phần liên thông đó; tập cạnh chúng ta cần tìm sẽ là tập cạnh được tạo bởi các cạnh của các khung đó.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k \cdot (n + m \cdot \alpha(n)))~.
• Độ phức tạp bộ nhớ sẽ tương tự như trong Subtask 1, tức ~O(n + m)~.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion(const int n): roots(n, -1) {};

    void reload() {
        fill(roots.begin(), roots.end(), -1);
    }

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    vector<bool> removed(m);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (int t = 0; t < k; ++t) {
        result = 0;
        dsu.reload();

        for (int i = 0; i < m; ++i) {
            if (removed[i])
                continue;
            const auto &[w, u, v] = edges[i];
            if (dsu.unite(u, v)) {
                removed[i] = true;
                result += w;
            }
        }

        cout << result << '\n';
    }
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 3: Giới hạn: ~n \le 10^3, m \le 5 \times 10^5; k \le 10^4~

Ý Tưởng:

• Đặt ~S_{i, j}~ (với ~1 \leq i \leq k~ và ~0 \leq j \leq m~) là tập cạnh được chọn trong thao tác thứ ~i~ sau khi đã xét ~j~ cạnh trong danh sách các cạnh được sắp xếp theo trọng số giảm dần. Chi tiết và ví dụ:

  Lưu ý: Phần này trình bày chi tiết cách xác định tập cạnh ~S_{i, j}~ theo định nghĩa trên. Nội dung này có thể không bắt buộc phải đọc để hiểu ý tưởng chính, mà chỉ nhằm làm rõ hơn định nghĩa ~S_{i, j}~.

  Chi Tiết

  • Với ~j = 0~, ta có ~S_{i,j} = \emptyset~ vì chưa có cạnh nào được xét ở thời điểm bắt đầu thao tác thứ ~i~.
  • Với ~1 \leq j \leq m~, đặt ~e~ là cạnh thứ ~j~. Khi đó, ta có thể xác định ~S_{i, j}~ như sau:
    • ~S_{i, j} = S_{i, j - 1}~ nếu một trong hai điều kiện sau thỏa:
      • Cạnh ~e~ đã được chọn trước đó: ~\exists z ((1 \leq z < i) \land (e \in S_{z,j}))~
      • Việc thêm cạnh ~e~ sẽ tạo thành một chu trình trong tập hiện tại: ~S_{i, j - 1} \cup \{e\}~ chứa ít nhất một chu trình.
    • ~S_{i, j} = S_{i, j - 1} \cup \{e\}~ trong trường hợp còn lại.

  Ví dụ

  • Với test ví dụ thứ hai, các cạnh sau khi được sắp xếp giảm dần theo trọng số có thứ tự như sau:

    ~ \begin{array}{|c|*{8}{c|}} \hline \textbf{i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline e_i & (1,2) & (2,3) & (3,4) & (4,5) & (1,5) & (2,5) & (1,3) & (2,4) \\ \hline w_i & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 \\ \hline \end{array} ~

  • Giá trị ~S_{i, j}~ được tính như bảng sau:

    ~ \begin{array}{|c|*{3}{l|}} \hline \textbf{ j\i } & \textbf{1} & \textbf{2} & \textbf{3} \\ \hline 0 & \emptyset & \emptyset & \emptyset \\ \hline 1 & \{(1,2)\} & \emptyset & \emptyset \\ \hline 2 & \{(1,2), (2,3)\} & \emptyset & \emptyset \\ \hline 3 & \{(1,2), (2,3), (3,4)\} & \emptyset & \emptyset \\ \hline 4 & \{(1,2), (2,3), (3,4), (4,5)\} & \emptyset & \emptyset \\ \hline 5 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5)\} & \emptyset \\ \hline 6 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5)\} & \emptyset \\ \hline 7 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3)\} & \emptyset \\ \hline 8 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3), (2, 4)\} & \emptyset \\ \hline \end{array} ~

• Ta nhận thấy rằng nếu cạnh thứ ~j~, gọi là ~e_j~, được chọn trong bất kì một thao tác ~i~ nào thì ~i~ chính là giá trị nhỏ nhất sao cho với mọi thao tác ~z~ trước ~i~ (~1 \leq z < i~), việc thêm ~e_j~ vào ~S_{z, j - 1}~ sẽ tạo thành chu trình. Nếu không, cạnh ~e_j~ đã nên được chọn trước thao tác ~i~. Ta có: ~i = \min\{x \mid \forall z ((1 \leq z < x) \rightarrow C(S_{z, j - 1} \cup \{e_j\})) \}~ với ~C~ là mệnh đề "đồ thị con tạo bởi tập cạnh ~A~ chứa ít nhất một chu trình".

• Dựa vào nhận xét trên, ta có thể duyệt qua từng cạnh và dùng kỹ thuật chặt nhị phân để xác định thao tác sớm nhất có thể chứa cạnh đó mà không tạo chu trình. Để kiểm tra việc một chu trình có thể xuất hiện hay không khi thêm một cạnh nào đó, với mỗi thao tác, ta sử dụng một cấu trúc dữ liệu để quản lý thành phần liên thông trong suốt quá trình duyệt qua các cạnh. Ý tưởng cài đặt: Ta có thể sử dụng ~k~ cấu trúc dữ liệu Disjoint Set Union để quản lý thành phần liên thông giữa ~n~ đỉnh cho ~k~ thao tác.

Độ Phức Tạp:

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k \cdot n + m \log k \cdot \alpha(n))~.

  Giải thích:

  • Bước sắp xếp cạnh có độ phức tạp ~O(m \log m)~ (tương tự như trong Subtask 1).
  • Việc khởi tạo ~k~ cấu trúc dữ liệu Disjoint Set Union để quản lý thành phần liên thông trên ~n~ đỉnh có độ phức tạp ~O(k \cdot n)~.
  • Bước xử lý các cạnh có độ phức tạp ~O(m \log k \cdot \alpha(n))~.
    • Với mỗi lần xét cạnh, chúng ta tìm được thao tác (nếu tồn tại) mà chứa được cạnh đang xét sau tối đa ~O(\log k)~ bước chặt nhị phân.
    • Với mỗi lần chặt nhị phân, việc kiểm tra việc hai đỉnh của cạnh đang xét có đang thuộc cùng một thành phần liên thông có độ phức tạp ~O(\alpha(n))~ (tương tự như trong Subtask 1).
    • Chúng ta phải xét qua ~O(m)~ cạnh.
    • Ngoài ra, chúng ta có thể phải cập nhật thành phần liên thông cuối mỗi lần xét cạnh với độ phức tạp ~O(\alpha(n))~.

Độ phức tạp tổng vì thế là ~O(m \cdot (\log k \cdot \alpha(n) + \alpha(n))) = O(m \log k \cdot \alpha(n))~

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(m + k \cdot n)~. Giải thích:
  • Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ (tương tự như trong Subtask 1).
  • Lưu ~k~ cấu trúc dữ liệu Disjoint Set Union cần ~O(k \cdot n)~ bộ nhớ.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<DisjointSetUnion> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1, DisjointSetUnion(n + 1));

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Subtask 4: Giới hạn: ~n \le 10^5, m \le 5 \times 10^5; k \le 10^4~

Ý Tưởng:

Lưu ý: Ý tưởng chính sử dụng trong Subtask này cũng giống như trong Subtask 3. Điểm khác biệt chính nằm ở hướng cài đặt ý tưởng.

• Nhận xét về độ phức tạp của cách cài đặt cho Subtask 3: Với độ phức tạp của cách cài đặt cho Subtask 3, ta nhận thấy rằng việc quản lý các thành phần liên thông cho từng thao tác, là phần có chi phí tính toán nặng trong trường hợp tệ nhất (với độ phức tạp ~O(k \cdot n)~). Mặt khác, các bước xử lý còn lại có chi phí tính toán chấp nhận được. Vì vậy, nếu ta muốn cải thiện ý tưởng đó, ta cần phải tối ưu những bước xử lý liên quan tới quản lý thành phần liên thông.

• Ta có một số nhận xét như sau:

  • Với cách cài đặt đề cập trong Subtask 3, ta cần phải quan lý tổng cộng ~k \cdot n~ đỉnh (mỗi cấu trúc dữ liệu Disjoint Set Union quản lý ~n~ đỉnh). Tuy nhiên, trong suốt quá trình xử lý ~m~ cạnh, chỉ có tối đa ~2 \cdot m~ đỉnh thuộc các thành phần liên thông có kích thước lớn hơn ~1~. Giải thích: Mỗi cạnh được xét nếu được thêm vào chỉ có thể làm tăng số lượng đỉnh nằm trong một thành phần liên thông không đơn lẻ thêm tối đa ~2~ đỉnh.

  • Khi kiểm tra hai đỉnh ~u~ và ~v~ khác nhau có thuộc cùng một thành phần liên thông hay không, ta nhận thấy rằng: nếu một trong hai đỉnh thuộc một thành phần có kích thước bằng ~1~ thì ~u~ và ~v~ chắc chắn không cùng thành phần liên thông. ~\Rightarrow~ Dựa trên những nhận xét trên, ta chỉ cần quản lý các thành phần liên thông có kích thước ít nhất là ~2~ đỉnh, và xử lý riêng các trường hợp thành phần liên thông chỉ có một đỉnh. Về mặt cài đặt, ta chỉ cần thêm đỉnh vào cấu trúc dữ liệu Disjoint Set Union khi ta cần gộp thành phần liên thông của đỉnh đó với đỉnh khác.

Độ Phức Tạp

• Ý tưởng trên có thể được cài đặt với độ phức tạp ~O(m \log m + k + m \log k \cdot \alpha(n))~. Giải thích:

  • Việc quản lý các thành phần liên thông giờ đây chỉ có độ phức tạp ~O(k)~ để khởi tạo và ~O(m)~ để thêm đỉnh khi xử lý tất cả ~m~ cạnh. Vì thế độ phức tạp tổng của cách cài đặt là ~O(m \log m) + O(k) + O(m) + O(m \log k \cdot \alpha(n)) = O(m \log m + k + m \log k \cdot \alpha(n))~

• Với cách cài đặt này, độ phức tạp bộ nhớ là ~O(m + k)~. Giải thích:

  • Lưu danh sách cạnh chiếm cần ~O(m)~ bộ nhớ như trong Subtask 1.
  • Lưu ~k~ cấu trúc dữ liệu Disjoint Set Union cần ~O(k)~ bộ nhớ và cần thêm ~O(m)~ bộ nhớ do chúng ta có thể thêm tối đa ~2 \cdot m~ đỉnh. ~\Rightarrow~ Độ phức tạp tổng của cách cài đặt là ~O(m) + O(m) + O(k) = O(m + k)~.

Code Minh Họa:

#include <bits/stdc++.h>
using namespace std;

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int addVertex() {
        const int result = roots.size();
        roots.push_back(-1);
        return result;
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

class UndirectedGraph {
private:

    unordered_map<int, int> ids;
    DisjointSetUnion dsu;

public:

    bool checkConnected(const int x, const int y) const {
        const auto a = ids.find(x);
        if (a == ids.end())
            return false;
        const auto b = ids.find(y);
        if (b == ids.end())
            return false;
        return dsu.checkConnected(a -> second, b -> second);
    }

    int getID(const int x) {
        const auto a = ids.find(x);
        if (a == ids.end())
            return ids[x] = dsu.addVertex();
        return a -> second;
    }

    bool unite(const int x, const int y) {
        return dsu.unite(getID(x), getID(y));
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<UndirectedGraph> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1);

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

Tổng hợp các Team VNOI

Vậy là đã 2 tháng kể từ đợt tuyển TNV Gen 5, hãy cùng chúng mình điểm lại những hoạt động để lại nhiều dấu ấn của các bạn TNV trong thời gian qua nhé.

Team Cộng Đồng

Team Cộng Đồng – những người luôn âm thầm đứng sau, chăm chút cho mọi hoạt động truyền thông của VNOI. Trong nhiệm kỳ Gen 5, Team đã có nhiều đóng góp nổi bật trong việc lan tỏa hình ảnh và thành tích của thí sinh Việt Nam trên đấu trường quốc tế, góp phần quảng bá mạnh mẽ bộ môn lập trình thi đấu tới học sinh, sinh viên, giáo viên và phụ huynh trên toàn quốc, đặc biệt là trong công tác truyền thông cho ICPC. Chỉ trong vòng 03 tháng (từ đầu tháng 8 đến tháng 11), fanpage VNOI đã tăng từ 22 000 lên hơn 28 000 lượt theo dõi, đạt hơn 10 triệu lượt xem – minh chứng rõ ràng cho sức lan tỏa và hiệu quả hoạt động của Team Cộng đồng trong nhiệm kỳ này.

Trước thềm các vòng thi ICPC Vòng Miền tại Việt Nam, Team Cộng Đồng đã liên tục đẩy mạnh truyền thông và quảng bá cuộc thi trên nhiều nền tảng mạng xã hội, cũng như các kênh thông tin đại chúng. Nhờ những nỗ lực đó, ICPC Vòng Miền năm nay đã ghi nhận số lượng đội tuyển và thí sinh tham dự cao kỷ lục – phá vỡ những con số thống kê của hơn 10 năm tổ chức trước đó. Trong suốt ba tuần diễn ra kỳ thi, Team Cộng Đồng đóng vai trò là cầu nối uy tín giữa các bạn thí sinh tham gia và những người theo dõi kỳ thi và Ban Tổ chức OLP-ICPC Việt Nam. Các thành viên đã tích cực truyền tải thông tin, hướng dẫn và gửi thông điệp từ BTC đến thí sinh, góp phần đảm bảo kỳ thi được diễn ra minh bạch, công bằng và chuyên nghiệp, đặc biệt trong bối cảnh các vòng loại đang phải đối mặt với vấn đề sử dụng Trí tuệ nhân tạo (AI) trong kỳ thi.

Tại ICPC Quốc gia 2025, ban Truyền thông VNOI đã tích cực phối hợp cùng với các đơn vị truyền thông và các đơn vị đăng cai ICPC Quốc gia 2025 nhằm xây dựng các kế hoạch truyền thông, thiết kế ấn phẩm và sáng tạo nội dung để quảng bá cho kỳ thi tập trung cấp quốc gia lớn nhất năm 2025 của cộng đồng lập trình thi đấu Việt Nam.

Vào đầu tháng 11/2025, Team Cộng Đồng đã tham gia tháp tùng các đội thi và thí sinh Việt Nam tham dự The 2025 ICPC Asia Bangkok Regional, liên tục đưa tin và cập nhật hình ảnh, thành tích của các đội Việt Nam và quốc tế tại đấu trường khu vực Asia Pacific đầu tiên của mùa giải 2025-2026.

Team Wiki

Song song với hoạt động truyền thông sôi nổi của Team Cộng đồng, Team Wiki trong năm 2025 tiếp tục giữ vai trò quan trọng trong việc xây dựng và hoàn thiện kho tri thức học thuật của VNOI – nơi cung cấp nguồn tài liệu chất lượng, dễ tiếp cận cho các bạn yêu thích lập trình thi đấu.

Từ đầu Gen 5 đến nay, Team Wiki đã xuất bản bài viết đầu tiên – “Phi hàm Euler”, đánh dấu cột mốc khởi đầu cho chuỗi nội dung học thuật được biên soạn và chuẩn hóa. Bên cạnh đó, bài "Giải quyết bài toán LCA bằng DSU" cũng đang trong giai đoạn hoàn thiện và sẽ sớm được ra mắt trên Tạp chí VNOI trong thời gian tới.

Hiện nay, Team đang có tổng cộng 6 bài viết đang được 'chăm chút' để chờ xuất bản đến độc giả , bao gồm:

• 5 bài cho Wiki: Tham lam, Sắp xếp, Bao hàm – Loại trừ, Sinh test (Kỹ năng phòng thi OI), DP Knapsack
• 1 bài cho Tạp chí: DP Knapsack on Tree

Trong nửa đầu Gen 5.0, định hướng của Team Wiki là tập trung hoàn thiện toàn bộ các chủ đề cơ bản còn thiếu hoặc các bài viết cũ chưa đạt chất lượng mong muốn. Với mong muốn xây dựng một nguồn tài liệu lý thuyết có chất lượng tham khảo cao, dễ hiểu và nhất quán, giúp những bạn mới bắt đầu với lập trình thi đấu (CP) có thể học tập hiệu quả hơn. Sau khi hoàn thiện các mảng kiến thức nền tảng, Team sẽ mở rộng sang những chủ đề chuyên sâu và bài viết có độ khó cao hơn, phục vụ nhóm độc giả đã theo đuổi CP lâu năm. Giai đoạn này cũng hứa hẹn sẽ mang đến những nội dung phân tích sâu sắc, mang đậm dấu ấn học thuật của Gen 5.

Team Contest

Ngoài ra, Team Contest trong nhiệm kỳ Gen 5 mang tới cho cộng đồng lập trình nhiều contest vô cùng bổ ích, trong đó, Team đã tổ chức thành công hai contest lớn:

• Educational DP Advanced Contest Part 2
• Regular Contest 22

Không những thế, Team còn chuẩn bị và lên kế hoạch xuất bản ba contest thuộc chuỗi Coding Challenge, tiếp tục tạo sân chơi học thuật cho cộng đồng. Hiện tại, Team Contest đang có những định hướng mới dành cho các contest phục vụ cho VOI sắp tới, hướng tới mô hình tổ chức tối ưu và đem lại trải nghiệm luyện tập hiệu quả hơn. Song song với các kỳ thi mới, Team dự kiến sẽ phối hợp cùng Team Cộng đồng để quảng bá trở lại những contest Educational trước đây, vốn rất phù hợp với nhóm học sinh đang ôn luyện kiến thức ở mức VOI. Ngoài ra, Team sẽ tiếp tục duy trì tần suất tổ chức các contest Bedao Regular thường xuyên, nhằm duy trì sự sôi động và tính liên tục cho hoạt động luyện tập của cộng đồng.

Team Tech

Và cuối cùng, không thể không nhắc đến Team Tech – những người âm thầm đứng sau, vận hành toàn bộ hệ thống kỹ thuật của VNOI. Từ nền tảng Wiki, Contest cho đến hệ thống quản lý nội dung, Team Tech luôn đảm bảo mọi hoạt động của các Team khác diễn ra trơn tru, ổn định và an toàn. Đặc biệt trong Gen 5, Team Tech đã ghi dấu ấn mạnh mẽ với những con số ấn tượng trong các kỳ thi ICPC: 9870 lượt nộp bài tại ICPC Miền Trung 2025 và 4881 lượt nộp bài tại ICPC Miền Bắc 2025. Những con số này không chỉ thể hiện khối lượng công việc khổng lồ mà Team đã xử lý, mà còn minh chứng cho năng lực vận hành vượt trội và sự tin cậy của hệ thống kỹ thuật VNOI, vốn đã được cải thiện vượt bậc so với các mùa thi trước. Không dừng lại đó, Team Tech còn mở rộng hỗ trợ trong nhiều kỳ thi về AI như Viettel AI Race 2025 (của Tập đoàn Công nghiệp - Viễn thông Quân đội (Viettel)) hay cuộc thi Olympic Trí tuệ nhân tạo sinh viên Việt Nam.

Các tình nguyện viên Gen 5 còn có cơ hội tham gia kỳ thi ICPC với vai trò Thanh tra - Giám sát tại 13 điểm thi tập trung toàn quốc theo yêu cầu từ BTC OLP-ICPC Việt Nam để đảm bảo một môi trường thi đấu lành mạnh, trong sạch, công bằng của hơn 491 đội thi và 1473 thí sinh.

Từ truyền thông, học thuật đến tổ chức và kỹ thuật, bốn Team của VNOI Gen 5 đã cùng nhau tạo nên một bức tranh toàn diện – nơi đam mê, sáng tạo và tinh thần cống hiến hòa làm một. Đằng sau mỗi bài viết, mỗi sự kiện, mỗi dòng code là nhiệt huyết và lòng tận tâm của các tình nguyện viên – những người trẻ luôn nỗ lực vì một cộng đồng lập trình thi đấu lớn mạnh hơn từng ngày. Gen 5 không chỉ là thể hiện cho một nhiệm kỳ TNV, mà là một hành trình trưởng thành của cả tập thể VNOI nói chung, nơi mỗi người góp một phần nhỏ để cùng hướng đến mục tiêu lớn: "Xây dựng một cộng đồng Tin học Việt Nam năng động, đoàn kết và cùng phát triển"

Tư liệu cũ

Giới thiệu

Tạp chí VNOI định kỳ sẽ quay trở lại cùng chuyên mục giới thiệu các bài viết, tư liệu học thuật và các contest luyện tập được chuẩn bị bởi các thế hệ Tình nguyện viên VNOI trong suốt 5 năm vừa qua. Với mong muốn góp phần cung cấp nguồn tài liệu và bài tập đáng tin cậy cho cộng đồng học sinh, sinh viên yêu thích lập trình thuật toán, chuyên mục được biên tập nhằm giúp độc giả ôn luyện và nghiên cứu từ những kiến thức cơ bản đến nâng cao để hướng tới các kỳ thi lập trình trong nước và quốc tế.

Các tài liệu và contest về chủ đề Hình học

Hình học tính toán luôn được xem là một trong những chủ đề khó và thử thách nhất trong lập trình thi đấu. Khác với các chủ đề thuần toán rời rạc như Quy hoạch động hay Đồ thị, hình học đòi hỏi khả năng xử lý số thực chính xác cùng tư duy trực quan không gian. Chính vì vậy, các bài toán hình học thường được xếp ở vị trí bài khó nhất trong nhiều kỳ thi APIO, IOI, ICPC hay kỳ thi chọn học sinh giỏi quốc gia.

Các bài toán hình học luôn đòi hỏi người giải phải xét rất nhiều trường hợp xử lý khi tiếp cận bài toán, xử lý các trường hợp biên (edge case) đối với các mô hình phẳng hoặc mô hình không gian cũng như đòi hỏi tính cẩn thận khi xử lý sai số số thực. Các bài toán hình học luôn yêu cầu cách triển khai rất phức tạp, dễ gặp lỗi và buộc người giải phải tốn rất nhiều thời gian giải quyết dưới áp lực của môi trường thi đấu.

Nhằm hỗ trợ cộng đồng người học tiếp cận chủ đề này một cách hệ thống, các Tình nguyện viên Team Wiki đã biên soạn bộ bài viết về Hình học tính toán, tập trung truyền tải những kiến thức cốt lõi và phổ biến nhất về chủ đề này:

• Hình học tính toán phần 1: Những khái niệm cơ bản
• Hình học tính toán phần 2: Sự giao nhau của đường thẳng và các ứng dụng
• Hình học tính toán phần 3: Đa giác

Bên cạnh tư liệu lý thuyết, nền tảng chấm bài VNOJ cũng đã tổ chức các kỳ thi luyện tập theo chủ đề, cung cấp nguồn bài tập tiếng Việt uy tín và chất lượng, phục vụ quá trình rèn luyện kỹ năng giải các bài tập hình học:

• Educational Geometry Contest
• Educational Geometry Contest Part 2

Các tài liệu và contest về chủ đề Quy hoạch động

Quy hoạch động luôn là một trong những chủ đề cốt lõi và có phạm vi ứng dụng rộng nhất trong Lập trình thi đấu. Đây là kỹ thuật tối ưu hóa mạnh mẽ dựa trên việc chia nhỏ bài toán thành các bài toán con, tận dụng kết quả đã tính toán để đạt được hiệu quả thời gian.

Không chỉ yêu cầu tư duy logic và phân tích bài toán thành các bài toán con, chủ đề này còn đòi hỏi người học phải rèn luyện kỹ năng nhận diện mô hình, kỹ thuật tối ưu bộ nhớ, và đôi khi cần kết hợp với các chủ đề nâng cao như Cấu trúc dữ liệu, Toán học rời rạc, Bitmask hay Đồ thị. Với tính vận dụng và phân hóa cao, các bài toán Quy hoạch động luôn xuất hiện trong hầu hết các kỳ thi lập trình từ cấp khu vực cho đến quốc tế.

Trong suốt nhiều năm vừa qua, các Tình nguyện viên Team Wiki VNOI đã biên soạn hệ thống bài viết về Quy hoạch động trên VNOI Wiki, giúp độc giả từng bước xây dựng tư duy và tiếp cận các kỹ thuật từ cơ bản đến nâng cao. Các bài viết học thuật Tiếng Việt về chủ đề Quy hoạch động có thể được tìm thấy tại VNOI Wiki.

Song song với tài liệu lý thuyết, nền tảng chấm bài VNOJ cũng đã tổ chức các kỳ thi luyện tập chủ đề Quy hoạch động, được chọn lọc kỹ lưỡng và bám sát cấu trúc các đề thi lớn, giúp người học phát triển tư duy và rèn luyện kỹ năng giải bài toàn diện:

• Educational Dynamic Programming Advanced Contest Part 1
• Educational Dynamic Programming Advanced Contest Part 2

Các tài liệu và contest về chủ đề Đường đi Euler và HLD

Trong lập trình thi đấu, các bài toán giải quyết theo mô hình cây luôn đòi hỏi những kỹ thuật xử lý dữ liệu khó để đảm bảo hiệu quả thời gian và quản lý không gian dữ liệu một cách tối ưu. Hai trong số những kỹ thuật quan trọng và phổ biến nhất cho nhóm bài toán này là Đường đi Euler (Euler Tour) và Heavy-Light Decomposition (HLD).

Euler Tour là kỹ thuật biến một cây thành một dãy tuyến tính bằng việc “phẳng hóa” cấu trúc cây, cho phép áp dụng thêm các cấu trúc dữ liệu như Segment Tree hay Fenwick Tree để xử lý nhanh các truy vấn trên đoạn, đặc biệt là các truy vấn trên cây con. Đây là nền tảng của rất nhiều bài toán cây từ cơ bản đến nâng cao trong ICPC hay IOI.

Trong khi đó, Heavy-Light Decomposition là kỹ thuật phân chia cây thành các đường đi “nặng” - “nhẹ”, giúp chuyển các truy vấn trên đường đi giữa hai đỉnh bất kỳ về một số lượng nhỏ các truy vấn trên đoạn. HLD là một trong những kỹ thuật khó và quan trọng nhất trong xử lý truy vấn trên cây, thường xuất hiện trong các bài toán mang tính phân loại cao, yêu cầu người giải kết hợp khả năng tư duy với các cấu trúc dữ liệu mạnh mẽ để đạt hiệu năng tối ưu.

Nhằm hệ thống hóa và hỗ trợ người học tiếp cận hai kỹ thuật thiết yếu này, các Tình nguyện viên Team Wiki đã biên soạn các bài viết hướng dẫn chi tiết trên VNOI Wiki:

• Heavy-Light Decomposition (HLD)
• Đường đi Euler trên cây

Bên cạnh nguồn tư liệu lý thuyết, các Tình nguyện viên Team Contest VNOI tổ chức một contest luyện tập theo chủ đề nhằm giúp người học nắm vững kiến thức và sẵn sàng để vận dụng các kỹ thuật này:

• Educational Euler Tour and HLD Contest

Các tài liệu về chủ đề Cây tiền tố (Trie)

Trong lập trình thi đấu, cấu trúc dữ liệu Trie (còn gọi là cây tiền tố) là một trong những công cụ hiệu quả khi làm việc với tập hợp các xâu hoặc các tập hợp số (dưới dạng nhị phân). Khác với các cấu trúc dữ liệu truyền thống như cây tìm kiếm nhị phân hay bảng băm, Trie cho phép quản lý và truy vấn dữ liệu dựa trên từng ký tự/từng bit theo cấu trúc phân tầng, từ đó đạt được hiệu năng truy vấn vượt trội đối với các bài toán liên quan đến tiền tố hoặc các truy vấn nhiều lần trên tập dữ liệu lớn.

Cấu trúc dữ liệu Trie thường được ứng dụng trong các bài toán từ điển, tự động gợi ý trong văn bản, tối ưu truy vấn XOR, cũng như các bài xử lý chuỗi phức tạp trong những kỳ thi lớn. Trên những nền tảng cơ sở về kiến thức và cài đặt của Trie, Team Wiki của VNOI đã biên soạn và cập nhật bài viết hướng dẫn chi tiết về chủ đề này trên VNOI Wiki:

• Cây tiền tố - Trie

Các contest luyện tập thuộc Dự án sinh test các kỳ thi chính thức của VNOI

Dự án sinh test các kỳ thi chính thức của VNOI được triển khai nhằm tổng hợp các đề thi và bài toán lập trình từ những kỳ thi chọn đội tuyển Học sinh giỏi Quốc gia của các địa phương và đơn vị đào tạo, giúp học sinh và sinh viên có một nguồn luyện tập chuẩn mực và bám sát thực tiễn để chuẩn bị cho các kỳ thi học sinh giỏi các cấp. Qua việc số hóa bộ đề và tổ chức trên nền tảng thi trực tuyến VNOJ. Đội ngũ Tình nguyện viên Team Contest thuộc VNOI kỳ vọng dự án sẽ góp phần nâng cao khả năng tự ôn luyện của học sinh với sự mô phỏng sát với kỳ thi cấp tỉnh, cấp quốc gia và quốc tế.

Các kỳ thi đã được số hóa và tổ chức lại trên hệ thống VNOJ trong khuôn khổ dự án:

• Kỳ thi chọn Đội tuyển HSGQG Thừa Thiên Huế 2023–2024
• Kỳ thi chọn Đội tuyển HSGQG Quảng Trị 2024–2025

Coding Challenge

Coding Challenge là một chuyên mục thuộc Tạp chí VNOI, được xây dựng với mục tiêu mang đến cho cộng đồng lập trình thi đấu Việt Nam một sân chơi hữu ích và thiết thực nhằm giúp các độc giả củng cố kiến thức thuật toán và thúc đẩy tinh thần học hỏi, chia sẻ trong cộng đồng.

Hoạt động được tổ chức định kỳ hai lần mỗi tháng trên Fanpage VNOI, Group Facebook “Diễn đàn Tin học Việt Nam” và nền tảng chấm bài trực tuyến VNOJ. Toàn bộ các bài toán trong Coding Challenge được biên soạn bởi đội ngũ Tình nguyện viên thuộc Team Contest của VNOI. Chất lượng các bài toán Coding Challenge được đảm bảo về tính chuyên môn, có sự đa dạng về chủ đề và độ khó cũng như đáp ứng yêu cầu về tính chặt chẽ và chính xác.

Độc giả của Tạp chí VNOI có thể tham gia giải các bài toán thuộc Coding Challenge và gửi lời giải về cho Tạp chí. Những bài giải chất lượng sẽ được chọn lọc để đăng tải trong các số Tạp chí tiếp theo. Bên cạnh việc được ghi nhận và giới thiệu rộng rãi đến cộng đồng, các tác giả có lời giải được đăng tải sẽ nhận những phần quà tri ân từ VNOI nhằm khuyến khích tinh thần ham học hỏi và chia sẻ kiến thức đến cộng đồng

Các lời giải được chọn lọc để đăng công khai sẽ được đánh giá dựa trên tiêu chí về sự rõ ràng, mạch lạc, sáng tạo; có sự đầu tư trong diễn giải tư duy, cấu trúc và tính dễ hiểu. Đối với các bài toán có nhiều subtask, tác giả cần trình bày đầy đủ ý tưởng và hướng giải quyết cho tất cả các phần.

Phần thưởng dành cho mỗi lời giải được đăng tải trên Tạp chí là một bộ quà tặng gồm sổ tay, bút, sticker và móc khóa. Đặc biệt, với các tác giả có từ 03 bài giải trở lên được đăng trong chuyên mục, Ban biên tập Tạp chí sẽ gửi tặng một chiếc áo VNOI như lời tri ân cho những đóng góp tích cực đối với Coding Challenge.

Sau 03 số đầu tiên, Coding Challenge đã ghi nhận những kết quả rất ấn tượng. Đã có tổng cộng 2316 lượt nộp bài trên hệ thống và 26 lời giải chất lượng được gửi về cho Tạp chí. Đây là nguồn động lực to lớn để đội ngũ Tạp chí VNOI tiếp tục phát triển và mở rộng sân chơi học thuật này trong thời gian tới.

Coding Challenge #1

Coding Challenge #1 có tên là Đường đi. Đây là một bài toán về chủ đề đường đi ngắn nhất trên đồ thị, với điểm khác biệt là cách xây dựng tập cạnh thông qua các truy vấn nối và tô màu đỉnh.

Bài toán này chứng kiến 182 độc giả tham gia giải và 30 bài giải đạt điểm tuyệt đối. Đội ngũ Tạp chí VNOI xin phép chọn lọc ra 2 lời giải được các độc giả gửi về cho Tạp chí.

Đề Bài

Đề bài gốc có thể được đọc trên hệ thống VNOJ Coding Challenge #1 - Đường đi

Cho một đồ thị vô hướng gồm ~N~ đỉnh, ban đầu đồ thị này không có cạnh nào. Mỗi đỉnh thứ ~i~ được gán một màu ~c_i~. Bạn cần thực hiện lần lượt ~Q~ thao tác, mỗi thao tác thuộc một trong hai loại sau:

• Loại 1: 1 x y - nối toàn bộ các đỉnh có màu ~x~ với toàn bộ các đỉnh có màu ~y~.

• Loại 2: 2 u v - đổi màu của toàn bộ các đỉnh ~i~ có ~c_i = u~ thành ~c_i = v~.

Sau khi thực hiện xong tất cả các thao tác, hãy in ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị.

Input

• Dòng đầu tiên chứa hai số nguyên ~N, Q~ ~(1 \le N, Q \le 3 \times 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~c_1, c_2, ..., c_N~ - màu ban đầu của từng đỉnh ~(1 \le c_i \le N)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên ~t, x, y~ mô tả các thao tác ~(1 \le t \le 2, 1 \le x, y \le N)~.

Output

• In ra ~N~ số nguyên, số thứ ~i~ là độ dài đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~i~. Nếu không tồn tại đường đi, in ra ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

0 1 -1 1 2

Notes

• Ban đầu: chưa có cạnh nào;

• Thao tác 1 1 2: Nối toàn bộ đỉnh màu ~1~ với toàn bộ đỉnh màu ~2~ ~\Rightarrow~ Tạo cạnh giữa các đỉnh ~{1, 5}~ với ~{2, 4}~;

• Thao tác 2 3 2: Đổi toàn bộ đỉnh màu ~3~ thành màu ~2~ ~\Rightarrow~ Đỉnh ~3~ có màu ~2~;

• Thao tác 1 2 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~;

• Thao tác 1 1 3: Không có thay đổi gì vì không còn đỉnh nào có màu ~3~.

Sau cùng, đường đi ngắn nhất từ đỉnh ~1~ đến các đỉnh khác là:

• Đỉnh ~1~ ~\rightarrow~ chính nó: ~0~

• Đỉnh ~2~: ~1~ ~\rightarrow~ ~2~ (độ dài ~1~)

• Đỉnh ~3~: Không tồn tại đường đi (~-1~)

• Đỉnh ~4~: ~1~ ~\rightarrow~ ~4~ (độ dài ~1~)

• Đỉnh ~5~: ~1 \rightarrow 2 \rightarrow 5~ (độ dài ~2~)

Minh họa test ví dụ

Lời giải #1

Subtask 1

• Giới hạn bổ sung: ~N, Q \le 100~

Ý tưởng:

• Vì giới hạn của subtask này là nhỏ, chúng ta có thể giải quyết subtask này bằng cách thực hiện chính xác như những gì đề yêu cầu.

  • Với thao tác loại ~1~ với hai màu ~x~ và ~y~, chúng ta duyệt tuần tự để tìm tập các đỉnh có màu ~x~ và tập các đỉnh có màu ~y~ rồi với mỗi cặp đỉnh từ hai tập, ta thêm cạnh nối hai chiều giữa hai đỉnh.

  • Với thao tác loại ~2~ với hai màu ~u~ và ~v~, chúng ta duyệt tuần tự và gán màu ~v~ cho các đỉnh có màu ~u~

    ~ c[i] \leftarrow v \quad \forall \, (c[i] = u) ~

• Sau khi thực hiện xong tất cả các thao tác, để tìm ra độ dài đường đi ngắn nhất từ đỉnh ~1~ tới toàn bộ các đỉnh trong đồ thị, ta có thể sử dụng thuật toán BFS từ đỉnh ~1~ trên đồ thị không trọng số dựng được.

Độ phức tạp:

• Cách giải như trên có độ phức tạp về thời gian là ~O(Q \cdot N^2)~ trong trường hợp xấu nhất

  • Quá trình đọc dữ liệu có độ phức tạp về thời gian là ~O(N + Q)~

  • Với mỗi thao tác loại ~1~, vì mỗi màu có ~O(N)~ đỉnh có màu đó, ta sẽ phải xem xét qua ~O(N^2)~ cặp đỉnh cho hai màu ~x~ và ~y~.

  • Với mỗi thao tác loại ~2~, ta phải quyệt qua ~O(N)~ đỉnh.

  • Bước chạy thuật toán BFS sẽ có độ phức tạp về thời gian là ~O(N + |E|)~ với ~|E|~ là số cạnh của đồ thị sau khi ta đã dựng xong. Vì dữ liệu có thể chứa ~O(Q)~ thao tác loại ~1~, ta có ~|E| = O(Q \cdot N^2)~. Nói cách khác, bước xử lý tìm đường đi ngắn nhất có độ phức tạp ~O(Q \cdot N^2)~

• Tương tự, độ phức tạp bộ nhớ của cách giải trên là ~O(Q \cdot N^2)~ trong trường hợp tệ nhất bởi ta phải lưu ~O(Q \cdot N^2)~ cạnh đồng thời cùng một lúc

Code minh họa:

#include <bits/stdc++.h>

using namespace std;

template<class A, class B>
bool maximize(A &a, const B& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class A, class B>
bool minimize(A &a, const B& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

constexpr int MAX_N = 300'005, INF = 0X3F3F3F3F;

int N, Q, c[MAX_N];
vector<int> graph[MAX_N];
signed minimumDistance[MAX_N];

void addEdges(const int x, const int y) {
    for (int i = 1; i <= N; ++i) {
        if (c[i] != x)
            continue;
        for (int j = 1; j <= N; ++j) {
            if (c[j] != y)
                continue;
            graph[i].push_back(j);
            graph[j].push_back(i);
        }
    }
}

void changeColors(const int u, const int v) {
    for (int i = 1; i <= N; ++i)
        if (c[i] == u)
            c[i] = v;
}

void runBFS() {
    queue<int> q;

    minimumDistance[1] = 0;
    q.push(1);

    for (; !q.empty(); q.pop()) {
        const int &x = q.front();
        for (const int &y : graph[x])
            if (minimize(minimumDistance[y], minimumDistance[x] + 1))
                q.push(y);
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> Q;

    for (int i = 1; i <= N; ++i) {
        minimumDistance[i] = INF;
        cin >> c[i];
    }

    for (int q = 1, t = 0, x = 0, y = 0; q <= Q; ++q) {
        cin >> t >> x >> y;
        if (t == 1)
            addEdges(x, y);
        else
            changeColors(x, y);
    }

    runBFS();

    for (int i = 1; i <= N; ++i)
        cout << ((minimumDistance[i] < INF) ? minimumDistance[i] : (-1)) << ' ';

    cout << '\n';

    return 0;
}