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

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

(File IO): input:worldline.in output:worldline.out

Time Limits: 1500 ms Memory Limits: 262144 KB

Description

Input

Output

Sample Input

5 5

1 2

1 3

2 3

3 4

4 5

Sample Output

5

Data Constraint

Hint

样例解释

题解

不难发现，题目要求的就是每一个点到能到的点数减去已有的边数

直接暴力肯定不行

所以用bitset优化一下就好啦，维护每个点能到的点

代码

#include<cstdio>

#include<vector>

#include<bitset>

#define BITSET 30000

#define N 60010

using namespace std;

vector<long>out[N];

bitset<BITSET+10>a[N];

long in[N],b[N];

int main()

{   long n,m,x,y,i,j,to,tot,l,r;

    long long ans=0;

    freopen("worldline.in","r",stdin);

    freopen("worldline.out","w",stdout);

    scanf("%ld%ld",&n,&m);

    for(i=1;i<=m;i++){

        scanf("%ld%ld",&x,&y);

        out[x].push_back(y);

        in[y]++;

    }

    tot=0;

    for(i=1;i<=n;i++)

        if(!in[i])

            b[++tot]=i;

    for(i=1;i<=tot;i++)

        for(j=0;j<out[b[i]].size();j++){

            to=out[b[i]][j];

            if(--in[to]==0)

                b[++tot]=to;

        }

    for(l=1,r=BITSET;l<=n;l=r+1,r+=BITSET){

        for(i=1;i<=n;i++)

            a[i].reset();

        for(i=n;i>=1;i--){

            for(j=0;j<out[b[i]].size();j++){

                to=out[b[i]][j];

                a[b[i]]|=a[to];

            }

            ans+=a[b[i]].count();

            if(b[i]>=l&&b[i]<=r)

                a[b[i]][b[i]-l]=1;

        }

    }

    printf("%lld\n",ans-m);

    return 0;

}