P8250 交友问题 题解

RedLycoris · 2022-03-22 08:07:01 · 题解

2020年的J组模拟，2022年终于进主题库了

知识点：根号分治

subtask 1：

利用 map 存储，然后暴力。

时间复杂度: O(n^2\log n)

subtask 2:

对于每一个节点都开一个 bitset 存储邻接点。(设为 b_i )

查询用 b_u \ xor \ (b_u \ and \ b_v) 即可。xor 为按位异或，and 为按位与。

时间&空间复杂度: O(\frac{n^2}{\omega})

subtask 3:

考虑将 subtask 1 和 2 结合起来。

我们设定一个阈值 limit。

对于所有度数大于 limit 的节点，我们用 bitset。反之，我们用 map。

Code:

#include<bits/stdc++.h>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
#define ld long double
using namespace std;
const int mxn=2e5+5;
vector<int>g[mxn];
int n,m,q;
int lim;
vector<int>heavy;
int id[mxn];
vector<bitset<mxn> >T;
map<int,int>have[mxn];
int deg[mxn];
inline void solve(){
    scanf("%d%d%d",&n,&m,&q);
    //cerr<<lim<<'\n';
    for(ri i=1,u,v;i<=m;++i){
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
        ++deg[u];
        ++deg[v];
    }
    sort(deg+1,deg+n+1);reverse(deg+1,deg+n+1);
    lim=deg[min(n,(int)(sqrt(n)*6))];//根号处分治
    memset(id,-1,sizeof(id));
    for(ri i=1;i<=n;++i){
        if(g[i].size()>lim){
            heavy.push_back(i);
            id[i]=heavy.size()-1;bitset<mxn>newb;
            newb&=0;
            for(ri j=0;j<g[i].size();++j)newb[g[i][j]]=1;
            T.push_back(newb);
        }else{
            for(ri j=0;j<g[i].size();++j)have[i][g[i][j]]=1;
        }
    }
    for(ri i=1;i<=q;++i){
        ri u,v;scanf("%d%d",&u,&v);
        if(~id[u] and ~id[v]){  //对两个点是否是重点分类讨论
            bitset<mxn>tmp=T[id[u]]^(T[id[u]]&T[id[v]]);
            tmp[u]=0;tmp[v]=0;
            printf("%d\n",tmp.count());
        }else if(~id[u]){
            ri ans=0;
            for(ri j=0;j<g[v].size();++j)if(g[v][j]==u or g[v][j]==v or T[id[u]][g[v][j]])++ans;
            printf("%d\n",T[id[u]].count()-ans);
        }else if(~id[v]){
            ri ans=0;
            for(ri j=0;j<g[u].size();++j)if(g[u][j]!=u and g[u][j]!=v and !T[id[v]][g[u][j]])++ans;
            printf("%d\n",ans);
        }else{
            ri ans=0;
            for(ri j=0;j<g[u].size();++j)if(g[u][j]!=u and g[u][j]!=v and !have[v][g[u][j]])++ans;
            printf("%d\n",ans); 
        }
    }
}
int main(){
    solve();
    return 0;
}