[JSOI2019]精准预测

Myth丶恋晨 2023-10-11 05:23 17阅读 0赞

[题目][Link 1]

这么明显的限制条件显然是\\(\\text\{2-sat\}\\)

考虑按照时间拆点，\\((0/1,x,t)\\)表示\\(x\\)个人在时间\\(t\\)是生/死

有一些显然的连边

\\\[(0,x,t+1)->(0,x,t)\\\]

就是如果想在\\(t+1\\)时刻还是活着那必须在\\(t\\)时刻还活着

\\\[(1,x,t)->(1,x,t+1)\\\]

就是如果\\(t\\)时刻死了，那么\\(t+1\\)时刻也得是死的

对于第一种限制，显然是连\\((1,x,t)->(1,y,t+1)\\)，别忘了连对称边，就是\\(y\\)在\\(t+1\\)时刻活着，那么\\(x\\)在\\(t\\)时刻可不能死，于是\\((0,y,t+1)->(0,x,t)\\)

对于第二种限制，连\\((0,x,t)->(1,y,t)\\)，对称边连\\((0,y,t)->(1,x,t)\\)

发现按照上面的方式建图我们仅是点数就是\\(nT\\)级别，不能接受

发现每个人的生/死都连成了一条链，我们把上面每一其他边相连的点缩掉，这样图的点数就达到了\\(n+m\\)级别

简单分析我们发现这是一个\\(\\rm DAG\\)

要对每个人求出有多少个人能和他一起活到最后

首先如果第\\(i\\)个人，\\((0,i,T+1)\\)能走到\\((1,i,T+1)\\)，即\\(i\\)活着能推出\\(i\\)死了，于是\\(i\\)显然不能活着，自然也就不可能有点能和\\(i\\)一起活到最后。对于这样的点直接输出\\(0\\)即可。

否则，我们就看看如果这个点活着，那么能推出多少个点死了，即\\((0,i,T+1)\\)能到达多少种不同的\\((1,y,T+1)\\)，这是经典的有向图传递闭包问题，只能做到\\(\\rm bitset\\)复杂度。

那\\(\\rm bitset\\)复杂度就可以了，\\(O(\\frac\{m(n+m)\}\{w\})\\)大概就能过了。

但是这样\\((0,i,T+1)\\)可能没有办法走到那些必死点，我们把必死点做一个\\(\\rm bitset\\)，和\\(i\\)点的\\(\\rm bitset\\)取一个或就可了。

之后点数大概是\\(4\\times 10^5\\)级别，显然开不下这么大的\\(\\rm bitset\\)。考虑奇技淫巧，我们把\\(\\rm bitset\\)分段，多做几遍就好了

代码

#include<bits/stdc++.h>
    #define re register
    #define LL long long
    #define max(a,b) ((a)>(b)?(a):(b))
    #define min(a,b) ((a)<(b)?(a):(b))
    #pragma GCC optimize(3)
    #pragma GCC optimize("-fcse-skip-blocks")
    #define getchar() (S==TT&&(TT=(S=BB)+fread(BB,1,1<<15,stdin),S==TT)?EOF:*S++)
    char BB[1<<18],*S=BB,*TT=BB; 
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=4.6e5+1;
    const int W=10000;
    struct E{int v,nxt;}e[600005];
    int head[maxn],vis[maxn];
    std::bitset<10000> dp[maxn],g;
    std::vector<int> id[2][50001],ti[50001];
    int xx[100001],t[100001],yy[100001],op[100001];
    int n,m,T,cnt,num,chk[50001],ans[50001];
    inline void add(int x,int y) {e[++num].v=y;e[num].nxt=head[x];head[x]=num;}
    inline int find(int x,int c) {
        int l=0,r=ti[x].size()-1;
        while(l<=r) {
            int mid=l+r>>1;
            if(ti[x][mid]==c) return mid;
            if(ti[x][mid]<c) l=mid+1;else r=mid-1; 
        }
        return 0;
    }
    void dfs(int x) {
        if(vis[x]) return;vis[x]=1;
        for(re int i=head[x];i;i=e[i].nxt) 
            dfs(e[i].v),dp[x]|=dp[e[i].v];
    }
    void calc(int l,int r) {
        if(l>n) return;r=min(n,r);g.reset();
        for(re int i=1;i<=cnt;i++) vis[i]=0,dp[i].reset();
        for(re int i=l;i<=r;i++) 
            for(re int j=0;j<ti[i].size();++j)  
                dp[id[1][i][j]][i-l]=1;
        for(re int i=1;i<=n;i++) dfs(id[0][i][ti[i].size()-1]);
        for(re int i=l;i<=r;i++) if(dp[id[0][i][ti[i].size()-1]][i-l]) g[i-l]=1,chk[i]=1;
        for(re int i=1;i<=n;i++) {
            if(chk[i]) continue;
            int x=id[0][i][ti[i].size()-1];;
            ans[i]+=(dp[x]|g).count();
        }
    }
    int main() {
        T=read(),n=read(),m=read();
        for(re int i=1;i<=m;i++) {
            op[i]=read(),t[i]=read(),xx[i]=read(),yy[i]=read();
            ti[xx[i]].push_back(t[i]);
            ti[yy[i]].push_back(t[i]+(op[i]==1?0:1));
        }
        for(re int i=1;i<=n;i++) ti[i].push_back(T+1);
        for(re int i=1;i<=n;i++) {
            std::sort(ti[i].begin(),ti[i].end());
            ti[i].erase(std::unique(ti[i].begin(),ti[i].end()),ti[i].end());
            for(re int j=0;j<ti[i].size();++j) 
                id[0][i].push_back(++cnt),id[1][i].push_back(++cnt);
            for(re int j=0;j<ti[i].size()-1;++j)
                add(id[1][i][j],id[1][i][j+1]);
            for(re int j=ti[i].size()-1;j;--j)
                add(id[0][i][j],id[0][i][j-1]);
        }
        for(re int i=1;i<=m;i++) {
            int x=find(xx[i],t[i]),y;
            if(op[i]) {
                y=find(yy[i],t[i]);
                add(id[0][xx[i]][x],id[1][yy[i]][y]);
                add(id[0][yy[i]][y],id[1][xx[i]][x]);
            }
            else {
                y=find(yy[i],t[i]+1);
                add(id[1][xx[i]][x],id[1][yy[i]][y]);
                add(id[0][yy[i]][y],id[0][xx[i]][x]);
            }
        }
        calc(W+1,2*W);calc(4*W+1,5*W);calc(1,W);calc(3*W+1,4*W);calc(2*W+1,3*W);
        for(re int i=1;i<=n;i++,putchar(' ')) if(chk[i]) putchar('0');else printf("%d",n-1-ans[i]);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11564842.html

[Link 1]: https://www.luogu.org/problem/P5332