[Niuke challenge 47] C. conditions (BitSet acceleration Floyd)

Portal

The question ：

Given $n$ A picture of a point , Yes $m_1$ There must be an edge , Yes $m_2$ This edge must not exist .
give $Q$ Time to ask , Ask two points at a time $x$ and $y$, ask ：

• $x$ Whether it must reach $y$
• $x$ Is it possible to reach $y$

$(n\le 1000,Q\le 200000)$

practice ：

The first idea to be clear is to build two maps , One has only certain edges , A sheet includes certain existing edges and possible edges .
Then the reachability between points is preprocessed for both graphs , Finally, ask directly .

One idea is the reachability of directed graphs , We use it $SCC$ Find the strongly connected component , Then the shrinking point becomes $DAG$, And then you can do it .

But the idea of the problem solution seems to be better .
Directed graph we can use $floyd$ stay $o(n^3)$ Next, we deal with pairwise reachability , And then use $bitset$ Speed up , The final complexity is $o(n^3/w)$,$w$ by 64.

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bitset<1001>f[1001],f1[1001];
int mpp[1005][1005];
int main()
{
    
    int n,m1,m2,q;
    scanf("%d%d%d%d",&n,&m1,&m2,&q);
    for(int i=1;i<=m1;i++)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        mpp[a][b]=1;
    }
    for(int i=1;i<=m2;i++)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        mpp[a][b]=2;
    }
    for(int i=1;i<=n;i++)
    {
    
        for(int j=1;j<=n;j++)
        {
    
            if(i==j)f[i][j]=f1[i][j]=1;
            if(mpp[i][j]==1)
            {
    
                f[i][j]=1;
                f1[i][j]=1;
            }
            else if(mpp[i][j]==0)
            {
    
                f1[i][j]=1;
            }
        }
    }
    for(int k=1;k<=n;k++)
    {
    
        for(int i=1;i<=n;i++)if(f[i][k])
        {
    
            f[i]=f[i]|f[k];
        }
    }
    for(int k=1;k<=n;k++)
    {
    
        for(int i=1;i<=n;i++)if(f1[i][k])
        {
    
            f1[i]=f1[i]|f1[k];
        }
    }
    while(q--)
    {
    
        int a,b;
        scanf("%d%d",&a,&b);
        if(f[a][b])printf("Yes ");
        else printf("No ");
        if(f1[a][b])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}