题解：P14329 [JOI2022 预选赛 R2] 交易计划 / Trade Plan

zsj0228 · 2025-11-11 21:21:14 · 题解

思路

先将同色连通块用并查集维护，将连接异色连通块的边记录下来。离线询问，对于每两种颜色的连通块暴力加边，并查集维护即可。

code

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 10;

int n, m, k;
int edge[N][2];
int s[N];
int fa[N];

int find(int u)
{
    if (u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}

vector<int> nod[N];
int cnt;
struct node
{
    int u, v;
    int su, sv;
    int id;
    bool operator<(const node &x) const 
    {
        if (su != x.su) return su < x.su;
        return sv < x.sv;
    }
} edg[N], que[N];
int q;
int res[N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; ++ i) scanf("%d%d", &edge[i][0], &edge[i][1]);
    for (int i = 1; i <= n; ++ i) scanf("%d", &s[i]), fa[i] = i;
    for (int i = 1, fu, fv; i <= m; ++ i)
    {
        fu = find(edge[i][0]);
        fv = find(edge[i][1]);
        if (s[fu] == s[fv]) fa[fu] = fv;
    }
    for (int i = 1; i <= n; ++ i) 
        if (fa[i] == i) 
            nod[s[i]].push_back(i);
    for (int i = 1; i <= m; ++ i)
    {
        int fu = find(edge[i][0]);
        int fv = find(edge[i][1]);
        if (s[fu] != s[fv]) 
        {
            if (s[fu] > s[fv]) swap(fu, fv);
            edg[ ++ cnt] = (node){fu, fv, s[fu], s[fv], 0};
        }
    }
    sort(edg + 1, edg + cnt + 1);
    scanf("%d", &q);
    for (int i = 1, u, v, fu, fv; i <= q; ++ i)
    {
        scanf("%d%d", &u, &v);
        fu = find(u);
        fv = find(v);
        if (s[fu] > s[fv]) swap(fu, fv);
        que[i] = (node){fu, fv, s[fu], s[fv], i};
    }
    sort(que + 1, que + q + 1);
    int pos = 0;
    for (int i = 1; i <= q; ++ i)
    {
        if (que[i - 1] < que[i])
        {
            for (int j = 0; j < nod[que[i].su].size(); ++ j) fa[nod[que[i].su][j]] = nod[que[i].su][j];
            for (int j = 0; j < nod[que[i].sv].size(); ++ j) fa[nod[que[i].sv][j]] = nod[que[i].sv][j];
        }
        while (!(que[i] < edg[pos + 1]) && pos + 1 <= cnt)
        {
            if (que[i].su != edg[pos + 1].su || que[i].sv != edg[pos + 1].sv) ++ pos;
            else 
            {
                int fu = find(edg[pos + 1].u);
                int fv = find(edg[pos + 1].v);
                fa[fu] = fv;
                ++ pos;
            }
        }
        int fu = find(que[i].u), fv = find(que[i].v);
        if (fu == fv) res[que[i].id] = 1;
        else res[que[i].id] = 0;
    }
    for (int i = 1; i <= q; ++ i) printf("%d\n", res[i]);
    return 0;
}