CodeForces 506D Mr. Kitayuta's Colorful Graph

brute force ? 其实是平方分解。很容易想到的是每一个颜色建一个图，然后并查集维护一下连通性。

问题在于颜色有O(m)种，每种颜色的图点数都是O(n)的，因此并查集的空间只能重复利用。

但是可以把以O(m)的空间把有用的连通块信息保留下来。

之后的处理可以借鉴分块的思想。

记点v属于的连通块数量为b(v)，对于询问x,y ，根据点所在的连通块信息，可以以O(max(b(x),b(y)))的时间回答出来。

设置一个阀值B，对于b(v)>B，提前预处理，小于B的就暴力回答。

因为一条边最多增加两个b(v)值，所有b(v)的和是O(m)的。最多有m/B个v满足b(v)大于B，对于每个这样的v，O(m)历遍，O(m)的空间记录答案。

两部分的复杂度是O(m/B*m + B*q)，类似分块的取法，取B = m/sqrt(q)，复杂度为O(m*sqrt(q))。

/*********************************************************

*      --------------Alfheim--------------               *

*   author AbyssalFish                                   *

**********************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+, maxm = 1e5+;

int pa[maxn], rak[maxn];

int fd(int x)

{

    return pa[x]? pa[x] = fd(pa[x]): x;

}

inline void joint(int a,int b)

{

    int x = fd(a), y = fd(b);

    if(x != y){

        if(rak[x] < rak[y]){

            pa[x] = y;

        }

        else {

            pa[y] = x;

            if(rak[x] == rak[y]) rak[x]++;

        }

    }

}

int a[maxm],b[maxm];

bool vis[maxn];

int hd_c[maxn], nx_e[maxm];

inline void add_e(int cl,int i)

{

    nx_e[i] = hd_c[cl];

    hd_c[cl] = i;

}

typedef vector<int> Block;

typedef vector<int> v_int;

vector<Block> blc;

Block tmp[maxn];

v_int in_blk[maxn];

inline void add_blc(int x)

{

    if(!vis[x]){

        vis[x] = true;

        tmp[fd(x)].push_back(x);

    }

}

inline void dump(int x)

{

    if(tmp[x].size() > ){

        blc.push_back(tmp[x]);

        tmp[x].clear();

    }

    if(vis[x]){

        vis[x] = false;

        rak[x] = pa[x] = ;

    }

}

const uint32_t MAXB = ;

int ans[MAXB+][maxn];

int id[maxn];

//#define LOCAL

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    //cout<<(2*maxm/sqrt(2*maxm));

    int n,m,q;

    scanf("%d%d",&n,&m);

    uint32_t B = floor(*m/sqrt(*m));

    int i,j;

    for(i = ; i <= m; i++){

        scanf("%d%d%d",a+i,b+i,&j);

        add_e(j,i);

    }

    for(i = ; i <= m; i++){

        for(j = hd_c[i]; j; j = nx_e[j]){

            joint(a[j],b[j]);

        }

        for(j = hd_c[i]; j; j = nx_e[j]){

            add_blc(a[j]);

            add_blc(b[j]);

        }

        for(j = hd_c[i]; j; j = nx_e[j]){

            dump(a[j]);

            dump(b[j]);

        }

    }

    for(i = ; i < (int)blc.size(); i++){

        for(auto v: blc[i]){

            in_blk[v].push_back(i);

        }

    }

    int id_cnt = ;

    for(i = ; i <= n; i++){

        if(in_blk[i].size() > B){

            id[i] = ++id_cnt;

            for(auto b_id: in_blk[i]){

                for(auto v: blc[b_id]){

                    ans[id_cnt][v]++;

                }

            }

        }

    }

    scanf("%d",&q);

    while(q--){

        int x,y; scanf("%d%d",&x,&y);

        int res;

        if(id[x]) res = ans[id[x]][y];

        else if(id[y]) res = ans[id[y]][x];

        else {

            res = i = j = ;

            v_int &X = in_blk[x], &Y = in_blk[y];

            n = X.size(); m = Y.size();

            while(i < n && j < m){

                if(X[i] == Y[j]){

                    res++; i++; j++;

                }

                else {

                    X[i] < Y[j] ? i++ : j++;

                }

            }

        }

        printf("%d\n",res);

    }

    return ;

}

巴特西

CodeForces 506D Mr. Kitayuta's Colorful Graph

最新文章

热门文章