CF506D

一念之间、、 · 2021-09-13 18:56:42 · 题解

这里提供另外一种不同的做法： bitset +小型暴力

想到对于每个颜色连通块，如果询问点同时属于一个颜色连通块集合，则贡献+1。

想法是对于每个点找到属于的连通块，用 bitset 合并计算贡献。

发现颜色连通块个数可能达到 m 级别为 10^5 ， bitset 开不下，考虑优化，一个简单的想法是对于数量较小的连通块可以暴力 O(n^2) 使用 map 储存。

设连通块大小为 s

于是，当 s\le10 的时候选择 O(n^2) 处理出节点，放进 map ，剩下的 s\ge 10^{5-1} = 10^4 使用 bitset 储存，复杂度 10^2\times \log n+10^{5+4}/64轻松跑过。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return*s++;}
//#define getchar gc
ll read()
{
    char c;
    ll w=1;
    while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
    ll ans=c-'0';
    while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
    return ans*w;
}
bitset<10005>bit[100005];
map<pair<int,int>,int>mp;//n^2部分，总数不多 
const int xx=1e5+5;
int n,m,fa[xx],vis[xx];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node{int a,b,c;bool operator<(const node&w)const{return c<w.c;};}e[xx];
vector<int>v[xx];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++)e[i].a=read(),e[i].b=read(),e[i].c=read();
    sort(e+1,e+m+1);
    int tt=0;
    for(int i=1;i<=m;i++)
    {
        int l=i,r=i;
        while(r<m&&e[r+1].c==e[r].c)r++;
        vector<int>use;
        for(int j=l;j<=r;j++)
        {
            if(!vis[e[j].a])use.push_back(e[j].a),vis[e[j].a]=1;
            if(!vis[e[j].b])use.push_back(e[j].b),vis[e[j].b]=1;
        }
        for(auto it:use)vis[it]=0,fa[it]=it;
        for(int j=l;j<=r;j++)fa[find(e[j].a)]=find(e[j].b);
        for(auto it:use)v[find(it)].push_back(it);
        for(auto it:use)
        {
            if(v[it].size())
            {
                if(v[it].size()<=10)
                {
                    for(auto a:v[it])
                    {
                        for(auto b:v[it])
                        {
                            if(a>=b)continue;
                            mp[make_pair(a,b)]++;
                        }
                    }
                }
                else 
                {
                    tt++;
                    for(auto a:v[it])bit[a][tt]=1;
                }
                v[it].clear();
            }
        }
        i=r;
    }
    int q=read();
    while(q--)
    {
        int a=read(),b=read();
        if(a>b)swap(a,b);
//      cout<<mp[make_pair(a,b)]<<"\n";
        cout<<mp[make_pair(a,b)]+(bit[a]&bit[b]).count()<<"\n";
    }
    return 0;
}