世界线 【NOIP2017提高A组模拟8.22】

题目

输入

输出

Sample Input

5 5
1 2
1 3
2 3
3 4
4 5

Sample Output

5

数据范围

---

思路

当时我还没看到是有向边，然后觉得并查集搞搞就好了。
后来发现后，琢磨了一下，发现，如果一点x能到间接到另一个点y，那么点x就得向y连一条边。然而dfs后却难以判重，gg

---

解法

竟然是用bitset这种东西，这题目真是。。。。
用bitset，把每一个点用一个二进制数来表示其能到达的点。例如：如果x能到达2好点，那么bit[x]里第2位改成1。
然而这样会爆炸空间。
那么分两次做，第一次处理小于n/2的点，第二次处理大于n/2的点。

---

代码

#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<bitset>
#define fo(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=6e4+50,maxm=1e5+5;
bitset<maxn/2> Bit[maxn];
int n,m,num,dad[maxn],go[maxm],fre[maxm],next[maxm],mid,bo,ans;
bool bz[maxn];

int read()
{
    int x=0; char c;
    for(c=getchar();c<'0'||c>'9';c=getchar());
    for(c;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
    return x;
}
void add(int x,int y)
{
    go[++num]=y;
    next[num]=fre[x];
    fre[x]=num;
}
void dfs(int x)
{
    if (!bo) {
        if (x<=mid) Bit[x].set(x);
    }
    else {
        if (x>mid) Bit[x].set(x-mid);
    }
    bz[x]=true;
    for(int i=fre[x];i;i=next[i]){
        if(!bz[go[i]]) dfs(go[i]);
        Bit[x]|=Bit[go[i]];
    }
}
int main()
{
    freopen("worldline.in","r",stdin);
    freopen("worldline.out","w",stdout);
    n=read(); m=read();
    fo(i,1,m){
        int x=read(),y=read();
        dad[y]=x;
        add(x,y);
    }
    mid=n/2;
    fo(i,1,n)
    if (!dad[i]) dfs(i);
    fo(i,1,n) {
        ans+=Bit[i].count();
        Bit[i].reset();
    }
    memset(bz,0,sizeof(bz));
    bo=1;
    fo(i,1,n)
    if (!dad[i]) dfs(i);
    fo(i,1,n) ans+=Bit[i].count();
    printf("%d\n",ans-m-n);
}