Editorial for Kết nối chơi game
Submitting an official solution before solving the problem yourself is a bannable offence.
1. Thuật trâu: Tìm kiếm nhị phân + DFS
ĐPT: ~O(m * n * \log q)~
Với mỗi màu ~c~ trong ~[1, m]~, ta có thể chặt nhị phân đáp án. Giả sử chặt nhị phân số ~k~ là số cạnh, ta tạo đồ thị từ ~k~ cạnh đầu tiên trong tập ~q~ cạnh, và đếm số đỉnh có màu ~c~ trong thành phần liên thông tạo ra.
2. Dijoints Sets + Small To Large
ĐPT: ~O(q * \log n * \log m)~
Sử dụng ~n~ map, với ý nghĩa : ~cnt_u~ chứa toàn bộ màu và số lượng màu đó trong thành phần liên thông chứa đỉnh ~u~
map <int, int> cnt[maxn];
2.1. Thuật trâu
Trường hợp đặc biệt: Nếu màu ~c~ chỉ có một đỉnh là ~u~ có chứa màu đó, thì ~ans[c] = 0~
Đối với trường hợp màu ~c~ có nhiều hơn một đỉnh: Cách làm thông thường với DSU là với mỗi cạnh ~u_i~ và ~v_i~, ta kiểm tra ~2~ đỉnh này có cùng thành phần liên thông hay không, nếu không cùng thành phần liên thông, ta có thể hợp ~2~ thành phần liên thông lại, bằng cách thêm toàn bộ màu và số lượng màu đó của thành phần liên thông chứa đỉnh ~v~ sang thành phần liên thông chứa đỉnh ~u~.
for (auto [color, w] : cnt[v]) {
cnt[u][color] += w;
}
Sau khi hợp màu ~c~ nào đó từ ~2~ thành phần lại khiến số màu của ~c~ trong thành phần liên thông bằng số lượng đỉnh có màu ~c~ ở đồ thị ban đầu, thì bước hợp cạnh thứ ~i~ vừa rồi chính là kết quả cho màu ~c~. Tuy nhiên lưu ý sẽ có trường hợp thành phần chứa ~v~ đủ màu, thành phần chứa ~u~ không có màu ~c~, thì chứng tỏ trước đó chúng ta đã có kết quả cho màu ~c~ rồi.
...
cnt[u][color] += w;
if (cnt[u][w] == số đỉnh màu c ban đầu && ans[c] != -1)
ans[c] = i;
...
2.2. Tối ưu bằng Small to large
Trường hợp xấu nhất đối với cách làm trâu phía trên, là với mỗi cạnh, thành phần chứa ~u~ có một đỉnh, thành phần chứa ~v~ bao gồm mọi đỉnh của ~i - 1~ cạnh phía trước, vậy số lần chuyển màu từ thành phần chứa ~v~ sang thành phần chứa ~u~ có độ phức tạp xấu nhất là ~O(n log m)~ và bộ nhớ là ~O(m)~. Vậy trường hợp xấu nhất của cả bài toán có thể khiến bộ nhớ lên đến ~O(m * q)~.
Vì vậy chúng ta sẽ chỉ hợp màu từ thành phần nhỏ hơn sang thành phần lớn hơn, như vậy độ phức tạp bộ sẽ giảm xuống chỉ còn ~O(q * log * m)~, và độ phức tạp thời gian là ~O(q * log(m) * log(n))~
u = get(u); v = get(v);
if (cnt[u].size() < cnt[v].size()) swap(u, v);
for (auto [color, w] : cnt[v]) {
...
}
2.3. Code
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, q, a[maxn];
int p[maxn], d[maxn], ans[maxn];
/// d[c] : Số đỉnh màu c trong đồ thị ban đầu
/// ans[c] : Kết quả cho màu c
map<int, int> cnt[maxn]; /// cnt[u] : Chứa tập màu c và số lượng tương ứng của màu c trong thành phần liên thông chứa u
int get(int u) {
return p[u] == u ? u : p[u] = get(p[u]);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[a[i]]++;
}
for (int i = 1; i <= m; i++)
ans[i] = -1;
for (int i = 1; i <= n; i++) {
p[i] = i;
cnt[i][a[i]]++;
if (d[a[i]] == 1) ans[a[i]] = 0; /// Trường hợp chỉ có một đỉnh có màu a[i]
}
for (int i = 1; i <= q; i++) {
int u, v;
cin >> u >> v;
u = get(u), v = get(v);
if (u != v) {
if (cnt[u].size() < cnt[v].size()) swap(u, v);
p[v] = u;
for (auto [color, w] : cnt[v]) {
cnt[u][color] += w;
if (cnt[u][color] == d[color] && ans[color] == -1)
ans[color] = i; /// Nếu hợp thành phần chứa u - v lại khiến số màu c bằng số màu trong đồ thị ban đầu, thì ta lưu lại kết quả cho màu c. Lưu ý nếu ans[c] != -1, chứng tỏ trước đó màu c đã đủ trong thành phần liên thông chứa v
}
}
}
for (int i = 1; i <= m; i++) {
cout << ans[i] << '\n';
}
return 0;
}
3. Parallel Binary search
ĐPT: ~O(q * \log q * \log n)~
3.1. Solutions
Từ thuật trâu sử dụng binary search phía trên, ta biết rằng với mỗi màu ~c~, chỉ cần không dùng quá ~log(q)~ bước để tìm ra kết quả. Với lần thứ ~i~ sử dụng ~q~ cạnh, ta sẽ tìm ra được một bộ ~l_i, r_i, mid_i~ tương ứng với màu thứ ~c~. Vì vậy ta có thể làm theo tư tưởng của chặt nhị phân song song, sau mỗi một lần dùng ~q~ cạnh, ta sẽ tìm ra bộ ~l_i, r_i, mid_i~ với mọi màu ~c~.
Với code của bài này mình sử dụng style chặt nhị phân ~while~ (~r - l > 1~) nên điều kiện dừng sẽ là nếu không tồn tại màu ~c~ nào có ~r[c] - l[c] > 1~ thì sẽ dừng việc xử lý lại.
Đầu tiên, gọi ~queries[i]~ là vector chứa các màu có thể có kết quả là ~mid = i~. Ta sẽ xử lý theo từng cạnh ~i~ từ ~0~ đến ~q~, với mỗi cạnh đó, ta sẽ nối thành phần chứa ~u_i, v_i~ tương ứng vào nhau.
Sau đó, ta sẽ kiểm tra các màu ~c~ nào có thể có kết quả ~mid = i~ (nằm trong vector ~queries[i]~)
Để kiểm tra mọi đỉnh có màu ~c~ có thuộc cùng thành phần liên thông hay không, ta sẽ dùng DSU, lưu các đỉnh có màu ~c~ vào trong vector ~colors[c]~, sau đó lấy ra gốc của các đỉnh này, nếu mọi gốc đều bằng nhau, chứng tỏ màu ~c~ đã cùng thành phần liên thông, ta gán ~r_c = i~, ngược lại gán ~l_c = i~
Sau khi dừng việc xử lý, in ra ~r_c~ tương ứng chính là kết quả cho từng màu.
3.2 Code
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, m, q, a[maxn], l[maxn], r[maxn];
int p[maxn];
int get(int x) {
return (x == p[x] ? x : p[x] = get(p[x]));
}
void unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) p[x] = y;
}
struct edge {
int u, v;
} b[maxn];
vector<int> colors[maxn];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
colors[a[i]].push_back(i);
}
for (int i = 1; i <= q; i++) cin >> b[i].u >> b[i].v;
for (int i = 1; i <= m; i++) {
l[i] = -1;
r[i] = q + 1;
}
for (;;) {
bool answered = 1;
vector<vector<int>> queries(q + 1);
for (int i = 1; i <= m; i++) {
if (r[i] - l[i] > 1) answered = 0;
queries[(l[i] + r[i]) / 2].push_back(i);
}
if (answered) break;
for (int i = 1; i <= n; i++) p[i] = i; /// reset DSU
for (int i = 0; i <= q; i++) {
if (i != 0) {
int u = get(b[i].u), v = get(b[i].v);
unite(u, v);
}
for (int color : queries[i]) {
int u = get(colors[color][0]);
bool ok = 1;
for (int id : colors[color]) {
int v = get(id);
if (u != v) ok = 0;
}
if (ok)
r[color] = i;
else
l[color] = i;
}
}
}
for (int i = 1; i <= m; ++i) {
if (r[i] == q + 1) r[i] = -1;
cout << r[i] << '\n';
}
return 0;
}
Comments