VOSPLAY - Kết nối chơi game

Có

$N$ học sinh và

$M$ trò chơi vi tính. Mỗi học sinh chỉ thích chơi một trò duy nhất và mỗi trò chơi có ít nhất một học sinh thích. Nhà trường tổ chức kết nối mạng LAN cho các máy trong

$Q$ phút, phút thứ

$i$nối

$2$ máy của học sinh

$U_i$ và

$V_i$ (coi như đồ thị vô hướng). Tất cả những học sinh thích chơi cùng một loại game sẽ bắt đầu chơi khi máy tính của họ liên thông (có thể đi qua các đỉnh chứa game khác). Hỏi thời gian bắt đầu chơi của mỗi game.
Nếu game chỉ có

$1$ người thích thì sẽ bắt đầu vào phút thứ

$0$
Nếu

$1$ loại game không thế liên thông sau

$Q$ phút thì in ra

$-1$ ứng với game đó

Input

Dòng

$1$:

$N$,

$M$,

$Q$ tương ứng với số học sinh, số trò chơi, số phút (mỗi phút nối

$1$ dây LAN)
Dòng

$2$: Gồm

$N$ số

$A_i$ miêu tả trò chơi mà học sinh thứ

$i$ thích

$Q$ dòng tiếp theo: mỗi dòng gồm

$2$ số

$U_i$ và

$V_i$

Output

Gồm

$M$ dòng, dòng thứ

$i$ là thời điểm bắt đầu chơi của game thứ

$i$

Giới hạn

$1\le N$,

$M\le {10}^5$.

$0\le Q\le {10}^5$

Input

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

Output

3
4

Solution

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 :

$cn{t}_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(nlogm)$ 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\ast 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\ast log\ast m)$, và độ phức tạp thời gian là

$O(q\ast log(m)\ast 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

/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#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]);}

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.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';
}

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,mi{d}_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,mi{d}_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

/*
	www.youtube.com/YugiHackerChannel
	oj.vnoi.info/user/YugiHackerKhongCopCode
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#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];

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> q;
    f1 (i, n)
    {
        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';
    }
}