# Lời giải bài SKILEVEL

## Tác giả: Lê Nguyễn Hữu An, T2124

## 1. Tóm tắt đề
Cho số nguyên dương $T$ và lưới vuông $m \times n$, ô vuông $(i,j)$ chứa một số nguyên $a_{ij}$. $(1 \le m, n \le 500;\ 1 \le T \le m \times n;\ 0 \le a_{ij} \le 10^9)$

Gọi $F(i, j)$ là số nguyên D **nhỏ nhất** sao cho từ ô $(i,j)$ có thể đi được đến **ít nhất** T ô trên ma trận. Hai ô **chung cạnh** là đi được đến nhau nếu $|a_{i_1j_1} - a_{i_2j_2}| <= D$.

Cho $q$ ô phân biệt $(i_1,j_1),\ (i_2, j_2)...(i_q, j_q)$. Hãy tính tổng $\sum_{k=1}^{q}F(i_k,j_k)$.

## 2. Lời giải
**Kiến thức cần biết:** **[DSU](https://vnoi.info/wiki/algo/data-structures/disjoint-set-union.md)**

Ta coi cạnh chung của hai ô $(i_1, j_1)$ và $(i_2, j_2)$ là một cạnh có trọng số $|a_{i_1j_1} - a_{i_2j_2}|$ nối $(i_1, j_1)$ với $(i_2, j_2)$.
Lưu tất cả những cạnh như vậy (có $2mn-m-n$ cạnh) và sắp xếp chúng lại.

**Ý tưởng**: Ta thêm từng cạnh theo thứ tự không giảm các trọng số vào cho đến khi các ô vuông được nối nhau có số lượng nhiều hơn hoặc bằng T. Vì cạnh được thêm theo thứ tự không giảm các trọng số, nên độ chênh lệnh nhỏ nhất giữa các ô vuông này chính là trọng số của cạnh vừa thêm vào.

**Thuật toán**:
- Ban đầu, mỗi ô vuông là một thành phần liên thông riêng biệt.
- Ta thêm từng cạnh theo trọng số không giảm vào.
- Nếu thành phần liên thông X có lực lượng nhỏ hơn T, sau khi thêm cạnh vào, đạt được lực lượng lớn hơn hoặc bằng T, thì với mọi ô vuông $(i,j)$ trong X (ban đầu) sẽ có $F(i,j) = w$ với $w$ là trọng số cạnh vừa được thêm vào.
- In ra tổng của những $F(i, j)$ được yêu cầu

**Độ phức tạp:** Ta cần sắp xếp các cạnh lại, do đó độ phức tạp là $O(m \times n \times log(m \times n))$
### Code mẫu: [Link](https://ideone.com/6B390K)