题解 CF1795G【Removal Sequences】

Graphcity · 2023-10-27 17:25:42 · 题解

不妨考虑时间倒流。显然最后被删去的点一定是 a_i=0 的点。那么这个点 x 所连接的所有边都一定要在它前面被选。也就是说，x 的所有邻居都会保留一条连向 x 的边到最后。将这些邻居的 a 值减去一之后，删掉 x，就变成了原来的一个子问题。然后用一个队列求解即可。

最后我们会连出来一个偏序的 DAG。如果两个点 (x,y) 不是美好的，当且仅当 x,y 之间有一条路径。问题转化为了求 DAG 上每个点能到达的点数。设 f_i 为 i 能到达的点集，则有 f_i=\cup_{i\to j}f_j。那么按照拓扑排序反着推，使用 bitset 求集合并即可。

交上去之后你会发现 MLE 了。解决办法也很粗暴，将值域分成常数个区间分开求解即可。时间复杂度 O(\dfrac{n^2}{\omega})。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=1e5,B=1e4;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

int T,n,m,a[Maxn+5],deg[Maxn+5],vis[Maxn+5]; ll ans;
vector<int> v[Maxn+5],w[Maxn+5];
bitset<B+5> f[Maxn+5];
queue<int> q;

inline void Clear()
{
    For(i,1,n) vector<int>().swap(v[i]);
    For(i,1,n) vector<int>().swap(w[i]);
    For(i,1,n) vis[i]=0;
}
inline void Solve()
{
    n=read(),m=read();
    For(i,1,n) a[i]=read(),deg[i]=0;
    For(i,1,m)
    {
        int a=read(),b=read();
        v[a].push_back(b),v[b].push_back(a),deg[a]++,deg[b]++;
    }
    For(i,1,n) if(a[i]==0) q.push(i);
    static int st[Maxn+5]; int top=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop(),vis[x]=1,st[++top]=x;
        for(auto y:v[x]) if(!vis[y])
        {
            a[y]--,w[x].push_back(y);
            if(!a[y]) q.push(y);
        }
    }
    ans=1ll*n*(n-1)/2;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(l+B,n);
        For(i,1,n) f[i].reset();
        For(i,l,r) f[i][i-l]=1;
        Rof(id,top,1)
        {
            int i=st[id]; for(auto j:w[i]) f[i]|=f[j];
            int k=f[i].count(); ans-=k;
        }
    }
    cout<<ans+n<<endl; Clear();
}

int main()
{
    T=read();
    while(T--) Solve();
    return 0;
}